70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Solution:

This is a Dynamic Programing problem.

We have 1 way to jump to step 1 and 2 ways to jump to step 2.

The ways to jump to step i is the ways to jump to step i - 1 plus the ways to jump to step i - 2.

In other words, from step i - 1, we have only 1 way to jump to step i, which is to jump 1 step.

From step i - 2, we also have only 1 way to jump to step i, which is to jump 2 steps.

Therefore, dp[i] = dp[i - 1] + dp[i - 2].

We can optimize the space by only use two variables to store the states.



Code:

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int n1 = 1;
        int n2 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = n1 + n2;
            n1 = n2;
            n2 = curr;
        }
        return n2;
    }
}