How would you solve the problem of climbing stairs (you can climb 1 or 2 steps at a time) using dynamic programming?

This is a classic problem that can be solved using dynamic programming. The problem can be formulated as follows:

You are climbing a stair that has ‘n‘ steps. At each step, you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

To approach this problem from a dynamic programming perspective, let’s denote ‘dp[i]‘ as the number of distinct ways to reach the ‘i-th‘ step. We want to compute the value ‘dp[n]‘, which will give us the total number of distinct ways to reach the top with ‘n‘ steps.

The base cases for this problem are when ‘n = 1‘ and ‘n = 2‘. If there is only one step, there is only one way to climb it: climbing one step. Similarly, if there are two steps, there are two ways to climb them: climbing two steps at once or climbing one step twice. So, we have:

dp[1] = 1
dp[2] = 2

For ‘n > 2‘, the number of distinct ways to reach step ‘n‘ can be computed from ‘dp[n-1]‘ and ‘dp[n-2]‘. This is because, from the ‘(n-1)-th‘ step, we can take one step to reach the ‘n-th‘ step, and from the ‘(n-2)-th‘ step, we can take two steps to reach the ‘n-th‘ step. This gives us:

dp[n] = dp[n-1] + dp[n-2]

With these equations, we can start filling up our ‘dp‘ array from ‘dp[1]‘ up to ‘dp[n]‘. Here’s a simple Python example:

def climbStairs(n):
    if n <= 2:
        return n
    dp = [0 for _ in range(n+1)]
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]

Using dynamic programming in this way, we achieve a time complexity of ‘O(n)‘ and a space complexity of ‘O(n)‘. However, since ‘dp[i]‘ only depends on ‘dp[i-1]‘ and ‘dp[i-2]‘, we can reduce the space complexity to ‘O(1)‘ by only keeping the last two calculated values:

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a+b
    return b

This solution maintains a similar time complexity ‘O(n)‘ but reduces the space complexity to ‘O(1)‘.