70. Climbing Stairs

Description of the Problem

You are climbing 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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: 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

Constraints:

• 1 <= n <= 45

Solution

Explanation

Consider climbing a n-step stairs, how many possible ways can we climb to the top. We have two possible move; either move 1 step or 2 step.

Thus the problem becomes finding the sum of the number of ways in (n-1)-step staircase and in (n-2)-step staircase. (see the following equations)

\[ \begin{align} w_0 = & \ 1 \\ w_1 = & \ 1 \\ w_n = & \ w_{n-1} + w_{n-2} \\ \end{align} \]

Code (Rust)

impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![0; n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for i in 2..=n{
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n] as i32;
    }
}

Complexity

Time complexity:

• \( T(n) = \Theta(n) \)

Auxiliary Space:

• \( S(n) = \Theta(n) \)