70. Climbing Stairs

Problem Statement

Easy

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

C++

Source file

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) return n;
        int prev = 2, prev2 = 1, res;
        for (int i = 3; i <= n; i++) {
            res = prev + prev2;
            prev2 = prev;
            prev = res;
        }
        return res;
    }
};

Java — dp memo

Source file

class Solution {
    public int climbStairs(int n) {
        Integer[] dp = new Integer[n+1];
        return solve(dp, n);
    }
    private int solve(Integer[] dp, int i){
        if(i==0)
            return 1;
        else if(i<0)
            return 0;
        if(dp[i]!=null)
            return dp[i];
        return dp[i] = solve(dp, i-1) + solve(dp, i-2);
    }
}

Java — dp optimized

Source file

class Solution {
    public int climbStairs(int n) {
        Integer[] dp = new Integer[n + 1];
        if (n < 3)
            return n;
        int ways1Step = 1, ways2Step = 2;
        for (int i = 3; i <= n; i++){
            int temp = ways1Step + ways2Step;
            ways1Step = ways2Step;
            ways2Step = temp;
        }
        return ways2Step;
    }
}

Java — dp tab

Source file

class Solution {
    public int climbStairs(int n) {
        Integer[] dp = new Integer[n+1];
        return solve(dp, n);
    }
    private int solve(Integer[] dp, int i){
        if(i==0)
            return 1;
        else if(i<0)
            return 0;
        if(dp[i]!=null)
            return dp[i];
        return dp[i] = solve(dp, i-1) + solve(dp, i-2);
    }
}

Java — iterative memo

Source file

class Solution {

    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        for (int i = 0; i < Math.min(n + 1, 3); i++)
            memo[i] = i;
        for (int i = 3; i <= n; i++)
            memo[i] = memo[i - 1] + memo[i - 2];
        return memo[n];
    }
}

Java — recursive memo

Source file

class Solution {
    int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return solve(n);
    }

    private int solve(int n) {
        if (n < 3)
            return n;
        if (memo[n] != 0)
            return memo[n];
        return memo[n] = solve(n - 1) + solve(n - 2);
    }
}

Java

Source file

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