0070 - Climbing Stairs

0070 - Climbing Stairs

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?

Examples:

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

1. 1 step + 1 step

2. 2 steps

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

Java Solution

Dynamic Programming

class Solution {
    public int climbStairs(int n) {
        if(n <= 1) return 1;

        int[] combinations = new int[n + 1];
        combinations[0] = 1;
        combinations[1] = 1;

        for(int i = 2; i <= n; i++) {
            combinations[i] = combinations[i-1] + combinations[i-2];
        }
        return combinations[n];
    }
}

Recursion (Compute values and store in lookup array)

class Solution {
    public int climbStairs(int n) {
        int[] lookup = new int[n+1];
        return helper(0, n, lookup);
    }
    
    public int helper(int i, int n, int[] lookup) {
        if(i > n) return 0;        
        if(i == n) return 1;       
        if(lookup[i] > 0) return lookup[i];
        
        lookup[i] = helper(i + 1, n, lookup) + helper(i + 2, n, lookup);
        return lookup[i];
    }
}