70. Climbing Stairs

DailyCodingProblem Amazon Hard

Problem

LeetCode

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

DailyCodingProblem

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters. For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

Solution

Recursion - O(2^N) time - O(n) space

using namespace std;
class Solution {
public:
    // A function that represents the answer to the problem for a given state
    int dp(int i) {
        if (i <= 2) return i; // Base cases
        return dp(i - 1) + dp(i - 2); // Recurrence relation
    }
    
    int climbStairs(int n) {
        return dp(n);
    }
}

Dynamic Programming Bottom-up - O(n) time - O(n) space

using namespace std;
class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        
        // An array that represents the answer to the problem for a given state
        int dp[n+1]; 
        dp[1] = 1; // Base cases
        dp[2] = 2; // Base cases
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2]; // Recurrence relation
        }
        
        return dp[n];
    }
}

Dynamic Programming Top-Down (Memoization)- O(n) time - O(n) space

using namespace std;
class Solution {
public:
    unordered_map<int, int> memo;
    
    int dp(int i) {
        if (i <= 2) return i;
        // Instead of just returning dp(i - 1) + dp(i - 2), calculate it once and then
        // store it inside a hashmap to refer to in the future
        if (!memo.contains(i)) {
            memo.put(i, dp(i - 1) + dp(i - 2));
        }
        
        return memo.get(i);
    }
    
    public int climbStairs(int n) {
        return dp(n);
    }
}