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

I: n=0
O: 1
I: n=1
O: 1
I: n=2
O: 2
O: n=3
O: f(0) + f(1) + f(2) = 1 + 1 + 2 = 4

Analysis

We can solve this recursively by prefix f(n) = f(n-3) + f(n-2) + f(n-1). But we spot overlapping subproblems. And we can frame this problem as an optimization problem so we also have optimal substructure. Yay! DP let's go. 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

Step 1 Define optimal subproblem
    climb(n) = maximum number of ways to climb to nth stair
Step 2 Solve by prefix
    climb(i) = climb(i-3) + climb(i-2) + climb(i-1)
Step 3 Base case
    climb(0) = 1
    climb(1) = 1
    climb(2) = 2
Step 4 Topo sort
    for i from 3 to n
Step 5 Final answer
    return climb(n)

Code

public int climbStairs2(int n) {
    // sanity check
    if (n < 0) return -1;
    if (n < 2) return 1;
    // init memo
    int[] climb = new int[n + 1];
    // base case
    climb[0] = 1;
    climb[1] = 1;
    climb[2] = 2;
    // topo order
    for (int i = 3; i <= n; i++) {
        climb[i] = climb[i-3] + climb[i-2] + climb[i-1];
    }
    // final answer
    return climb[n];
}

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

Compress Cache

There are only 3 layers of dependency. We don't have to store the entire cache.

int[] climb = new int[3];
...
climb[i % 3] = climb[(i-3) % 3] + climb[(i-2) % 3] + climb[(i-1) % 3];
...
return climb[n % 3];

The space complexity is only O(1).

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).