1D Dynamic Programming

Experience is just remembered effort.

Most people feel intimidated by DP because it seems like a complex topic, but once you learn to recognize the patterns, it becomes much more approachable. The key is to understand that DP is all about figuring out the recurrence relations and then optimizing the way you compute them.

As always, try this problem for 20-30 minutes to warmup your curiosity machinery, and then read the rest of the article to see how we can solve it efficiently.

Problem: Climbing Stairs (LeetCode Link): 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? 💡 Hint

The Naive Recursive Approach

The most direct way to think about this is with recursion. The number of ways to get to step n, let's call it ways(n), is the sum of the ways to get to the steps you could have come from: ways(n) = ways(n-1) + ways(n-2)

You might recognize this equation if you've seen the Fibonacci sequence before. The base cases are: ways(0) = 1 (one way to stay at the ground) and ways(1) = 1 (one way to take one step).

def climbStairs(n):
    if n <= 1:
        return 1
    return climbStairs(n - 1) + climbStairs(n - 2)

public int climbStairs(int n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

int climbStairs(int n) {
    if (n <= 1) return 1;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

This is simple and correct, but it's incredibly slow. If you call climbStairs(5), it will calculate climbStairs(3) twice, climbStairs(2) three times, and so on. This is the problem of overlapping subproblems.

The Core of DP: Remember Your Work

Dynamic Programming is simply a technique to avoid re-solving these overlapping subproblems. We do this by storing the results of subproblems in a cache (a hash map or an array) and reusing them. There are two main ways to apply this.

Strategy 1: Memoization (Top-Down DP)

This is the most intuitive upgrade from the naive recursive solution. We keep the recursive structure but add a cache to store results. Before computing ways(n), we check if we've already calculated it. If so, we return the cached value. If not, we compute it, store it in the cache, and then return it.

def climbStairs(n: int) -> int:
    memo = {}
    def solve(i):
        if i in memo:
            return memo[i]
        if i <= 1:
            return 1
        memo[i] = solve(i - 1) + solve(i - 2)
        return memo[i]
    return solve(n)

public int climbStairs(int n) {
    Map<Integer, Integer> memo = new HashMap<>();
    return solve(n, memo);
}
private int solve(int n, Map<Integer, Integer> memo) {
    if (memo.containsKey(n)) return memo.get(n);
    if (n <= 1) return 1;
    int result = solve(n - 1, memo) + solve(n - 2, memo);
    memo.put(n, result);
    return result;
}

int solve(int n, unordered_map<int, int>& memo) {
    if (memo.count(n)) return memo[n];
    if (n <= 1) return 1;
    int result = solve(n - 1, memo) + solve(n - 2, memo);
    memo[n] = result;
    return result;
}
int climbStairs(int n) {
    unordered_map<int, int> memo;
    return solve(n, memo);
}

Strategy 2: Tabulation (Bottom-Up DP)

Instead of starting from the top (n) and going down, we can start from the bottom and build our way up. We create a DP table (usually an array) and fill it out iteratively.

Define DP State: dp[i] will store the number of ways to reach step i.
Base Cases: dp[0] = 1 (one way to reach the start), dp[1] = 1 (one way to take one step).
Recurrence Relation: dp[i] = dp[i-1] + dp[i-2].
Iteration: We loop from i = 2 up to n, filling the table.

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

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

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

Space Optimization

For our climbStairs tabulation, notice that to calculate dp[i], we only need dp[i-1] and dp[i-2]. We don't need the rest of the array! This means we can optimize the space complexity from $O(N)$ to $O(1)$ by only storing the last two values.

def climbStairs(n: int) -> int:
    if n <= 1: return 1
    one_back, two_back = 1, 1
    for i in range(2, n + 1):
        current = one_back + two_back
        two_back = one_back
        one_back = current
    return one_back

public int climbStairs(int n) {
    if (n <= 1) return 1;
    int oneBack = 1, twoBack = 1;
    for (int i = 2; i <= n; i++) {
        int current = oneBack + twoBack;
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

int climbStairs(int n) {
    if (n <= 1) return 1;
    int oneBack = 1, twoBack = 1;
    for (int i = 2; i <= n; i++) {
        int current = oneBack + twoBack;
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

Nice! isn't it? Can you do the same for the other problems? Try it out!