Climbing stairs

Count the ways to climb n steps taking 1 or 2 at a time. The gentlest introduction to DP.

The idea

The last move onto step i was either a single step from i-1 or a double step from i-2. So the number of ways to reach i is the sum of the ways to reach those two.

Code

int climbStairs(int n) {
    vector<int> dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

def climb_stairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

public static int ClimbStairs(int n) {
    var dp = new int[n + 1];
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

Tips

• Define the state (dp[i] = ways to reach step i), the transition, and the base cases. Every DP problem has those three parts.
• Only the last two values are needed, so space can drop to O(1).

In the .NET library

int overflows silently at n = 46 here. Use long, or wrap the sum in checked(...) to get an OverflowException instead of a wrong answer.