Climbing Stairs

Question 1 (LC.70)

There are n stairs. Each time you can either take 1 step or 2 steps. How many distinct ways you can climb to the top?

Example

n = 1 => 1
n = 2 => 2
n = 3 => 3
n = 7 => 21

Follow Up #1

Can you do this in O(1) space?

Analysis

Notice the recurrence only uses memo[i-1], memo[i-2]. We can just use 2 constants to hold them. And update both during the tabulation.

Question 2 (LC.272)

There are n stairs. Each time you can either take 1 step or 2 steps or 3 steps. How many distinct ways you can climb to the top?

Example

n = 1 => 1
n = 2 => 2
n = 3 => 4
n = 7 => 44

Analysis

From the picture, subproblems are obviously overlapping. Therefore, we can memoize the answers for the subproblems to avoid redundant calls.
DP in 5 Easy Steps:

1. define subproblems - optimal substructures - prefix/suffix/substring/backpack/etc
2. recursive dp using the subproblems
3. topological order
4. initialize base cases
5. answer to the original problem

Approach

1. define by prefix
    climb(n) = number of distinct ways at stair n
2. solve by prefix
    In order to get to stair n, we have 3 options, from n-1 or n-2 or n-3
    climb(n) = climb(n-1) + climb(n-2) + climb(n-3)
3. topo order
    for i from 3 to n
4. base cases
    climb(1) = 1, climb(2) = 2, climb(3) = 1 + 2 + 1 = 4
5. answer
    return climb(n)

Code

public int climbStairs2(int n) {
    // edge case check
    if (n <= 1) {
        return 1;
    }
    if (n <= 2) {
        return 2;
    }
    // create memo table
    int[] memo = new int[n];
    // initialization
    memo[0] = 1;
    memo[1] = 2;
    memo[2] = 4;
    // topo order
    for (int i = 3; i < n; i++) {
        memo[i] = memo[i-1] + memo[i-2] + memo[i-3];
    }
    // answer
    return memo[n-1];
}

Time & Space Complexity

Time - O(n) cause one for loop from i = 3 to n Space - O(n) we have n subproblems and therefore need to store n partial answers

Question 3

There are n stairs. Each time you can either take 1, 2, 3, ..., or k steps. How many distinct ways you can climb to the top?

Analysis

k = 1, climb(n) = climb(n-1)
k = 2, climb(n) = climb(n-1) + climb(n-2)
k = 3, climb(n) = climb(n-1) + climb(n-2) + climb(n-3)
k = 4, climb(n) = climb(n-1) + climb(n-2) + climb(n-3) + climb(n-4)
k = k, climb(n) = climb(n-1) + climb(n-2) + climb(n-3) + climb(n-4) + ... + climb(n-k)

Code

public int climbStairsK(int n, int k) {
    // create memo table
    int memo = new int[n + 1];
    // init base case
    memo[0] = 1;
    // topo order
    for (int i = 1; i < n + 1; i++) {
        // calling all subproblems
        for (int j = k; j > 0; j--) {
            if (i >= j) {
                memo[i] += memo[i-j];
            }
        }
    }
    // answer
    return memo[n];
}

Time Complexity

The space is still O(n). What about time? O(n*k).