Number of Ways Up the Stair

Problem

This problem will act as a template to solving dynamic programming problems in our future problems. We will use these steps below to solve almost all of our dynamic programming problems.

Problem Description

You are climbing up a staircase. It takes $n$ steps to reach the top.

Each time you can either climb $1$ or $2$ steps.

In how many distinct ways can you climb to the top?

Given:

• 0 < n

Testcases

Input: n = 2
Output: 2

There are two ways to climb to the top:

1. 1 step + 1 step
2. 2 steps

Input: n = 3
Output: 3

There are three ways to climb to the top:

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

---

Solution

Subproblems

At the $n$-th step, there are two ways to get to the $n$-th step:

1. Take $1$ step from the $(n-1)$-th step.
2. Take $2$ steps from the $(n-2)$-th step.

After we found that the $n$-th step depends on the $(n-1)$-th and $(n-2)$-th step, we need to find the relationship between the $n$-th step and the $(n-1)$-th and $(n-2)$-th step.

Recurrence Relation

We can see that the number of ways to get to the $n$-th step is the sum of the number of ways to get to the $(n-1)$-th and $(n-2)$-th step. In more general terms, the problem is the sum of the subproblems.

Let $f(n)$ be the number of ways to get to the $n$-th step. We can form the recurrence relation as follows:

$$f(n) = f(n - 1) + f(n - 2)$$

Base Cases

We also need to consider the base cases, which are the first two steps.

1. There is $1$ way to get to the first step, i.e. take $1$ step.
2. There are $2$ ways to get to the second step, i.e. take $1$ step twice or take $2$ steps.

$$\begin{aligned} f(1) &= 1 \\ f(2) &= 2 \end{aligned}$$

Solving the Problem

We can solve the problem using the recurrence relation above, which is exactly the same as the Fibonacci sequence, with only differences in the base cases.

So with the bottom-up approach, we can solve the problem similar to the Fibonacci sequence. We will use a memoization array of size $n$, one-based index, because the smallest base case is $1$. Then, we can calculate the next values using the necessary previous values.

Number of Ways Up the Stair

function number_of_ways_up_the_stair(n: int) -> int {
    // initialize memoization array
    let dp = [...] of size n
             one-based index
    let dp[1] = 1
    let dp[2] = 2

    // calculate next values
    for i from 3 to n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[n]
}

Time complexity: $O(n)$
Space complexity: $O(n)$

The solution to the number of ways up the stair problem with $n = 5$.

Space Optimization

We can find that we only need the previous two values to calculate the next value, so we can optimize the space complexity to $O(1)$ by only storing the previous two values.

Number of Ways Up the Stair - Space Optimized

function number_of_ways_up_the_stair(n: int) -> int {
    // initialize base cases
    let prev = 1
    let curr = 2

    // exceptional case for n = 1
    if n == 1 {
        return prev
    }

    // calculate next values
    for i from 3 to n {
        let next = prev + curr
        prev = curr
        curr = next
    }

    return curr
}

Time complexity: $O(n)$
Space complexity: $O(1)$

The space optimized solution to the number of ways up the stair problem with $n = 5$.

Checkpoint

What is the main goal of forming the recurrence relation in the beginning?

To write the recursive function

To verify the correctness of the solution

To get the iterative solution

To find out the relationship between the problem and the subproblems

Implementation

Python

We will implement the solution similar to the Fibonacci sequence problem. However, we will use a memoization array of size $n + 1$ instead of $n$, because the problem is one-based index, and we don't want to complicate the code with the $-1$ offset. We will ignore the first element.

In your own implementation, you can use a memoization array of size $n$ and offset the index by $-1$.

Note that $n = 1$ is exceptional, because initializing the $2$-nd element will cause an index out of bounds error.

Number of Ways Up the Stair

def numberOfWaysUpTheStair(n):
    # exceptional case for n = 1
    if n == 1:
        return 1

    # initialize memoization list
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    # calculate next values
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Number of Ways Up the Stair - Space Optimized

def numberOfWaysUpTheStair(n):
    # initialize base cases
    prev = 1
    curr = 2

    # exceptional case for n = 1
    if n == 1:
        return prev

    # calculate next values
    for i in range(3, n + 1):
        next = prev + curr
        prev = curr
        curr = next

    return curr

C++

We will implement the solution similar to the Fibonacci sequence problem. However, we will use a memoization array of size $n + 1$ instead of $n$, because the problem is one-based index, and we don't want to complicate the code with the $-1$ offset. We will ignore the first element.

In your own implementation, you can use a memoization array of size $n$ and offset the index by $-1$.

Note that $n = 1$ is exceptional, because initializing the $2$-nd element will cause an index out of bounds error.

Number of Ways Up the Stair

#include <vector>

int number_of_ways_up_the_stair(int n) {
    // exceptional case for n = 1
    if (n == 1) {
        return 1;
    }

    // initialize memoization vector
    std::vector<int> dp(n + 1, 0);
    dp[1] = 1;
    dp[2] = 2;

    // calculate next values
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

Number of Ways Up the Stair - Space Optimized

int number_of_ways_up_the_stair(int n) {
    // initialize base cases
    int prev = 1;
    int curr = 2;

    // exceptional case for n = 1
    if (n == 1) {
        return prev;
    }

    // calculate next values
    for (int i = 3; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }

    return curr;
}

Rust

We will implement the solution similar to the Fibonacci sequence problem. However, we will use a memoization array of size $n + 1$ instead of $n$, because the problem is one-based index, and we don't want to complicate the code with the $-1$ offset. We will ignore the first element.

In your own implementation, you can use a memoization array of size $n$ and offset the index by $-1$.

Note that $n = 1$ is exceptional, because initializing the $2$-nd element will cause an index out of bounds error.

Number of Ways Up the Stair

fn number_of_ways_up_the_stair(n: usize) -> usize {
    // exceptional case for n = 1
    if n == 1 {
        return 1;
    }

    // initialize memoization vector
    let mut dp = vec![0; n + 1];
    dp[1] = 1;
    dp[2] = 2;

    // calculate next values
    for i in 3..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    dp[n]
}

Number of Ways Up the Stair - Space Optimized

fn number_of_ways_up_the_stair(n: usize) -> usize {
    // initialize base cases
    let mut prev = 1;
    let mut curr = 2;

    // exceptional case for n = 1
    if n == 1 {
        return prev;
    }

    // calculate next values
    for _ in 3..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }

    curr
}

---

Related Topics

LeetCode - Climbing Stairs: https://leetcode.com/problems/climbing-stairs/