Dynamic Programming (2D)

Fibonacci and climbing stairs both had state described by a single changing number — "how many steps," "which Fibonacci index." Many classic DP problems need two changing variables to describe a subproblem — "using only the first i items," "with capacity w left," or "comparing the first i characters of one string against the first j characters of another." Whenever you notice two independent quantities both shrinking/growing as you recurse, that's your signal to reach for a 2D dp table: dp[i][j] instead of dp[i].

Classic 1: 0/1 Knapsack

Problem: given n items, each with a weight and a value, and a knapsack with capacity W, choose a subset of items (each item taken whole or not at all — that's the "0/1") that maximizes total value without exceeding capacity W.

Defining the state: let dp[i][w] = the maximum value achievable using only the first i items with capacity w remaining. For each item i, there are exactly two choices: skip it (value stays whatever the first i−1 items could achieve with the same capacity), or take it (its value plus whatever the first i−1 items could achieve with the reduced capacity, only possible if it fits). The recurrence takes whichever choice is better:

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][w] — a fresh list per row, NOT [[0]*(capacity+1)]*(n+1),
    # which would alias every row to the same underlying list
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight = weights[i - 1]
        value = values[i - 1]

        for w in range(capacity + 1):
            if weight > w:
                dp[i][w] = dp[i - 1][w]  # can't fit item i, so skip it
            else:
                dp[i][w] = max(
                    dp[i - 1][w],                       # skip item i
                    value + dp[i - 1][w - weight]       # take item i
                )

    return dp[n][capacity]

Time complexity: O(n·W) — the table has (n+1)·(W+1) cells, each filled with O(1) work. Space complexity: O(n·W) for the full table. In practice this can be optimized to O(W) using a rolling 1D list, since row i only ever depends on row i−1, but the full 2D version is clearer for learning and for reconstructing which items were chosen.

Classic 2: Longest Common Subsequence (LCS)

Problem: given two strings, find the length of their longest subsequence common to both (characters in the same relative order, not necessarily contiguous).

Defining the state: let dp[i][j] = the length of the LCS of the first i characters of string A and the first j characters of string B. If the current characters match, they must both be part of the optimal LCS, so we extend the LCS of the strings without those characters. If they don't match, the best LCS is whichever is better: dropping the current character of A, or dropping the current character of B.

def longest_common_subsequence(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]  # row/col 0 stay 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # extend the match
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  # drop a char from A or from B

    return dp[n][m]

Time complexity: O(n·m) — the table has (n+1)·(m+1) cells, each filled with O(1) work. Space complexity: O(n·m) for the full table, optimizable to O(m) with a rolling list since row i only depends on row i−1 (though, as with knapsack, you'd lose the ability to reconstruct the actual subsequence without extra bookkeeping).