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:

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1]; // dp[i][w], rows default to 0

    for (int i = 1; i <= n; i++) {
        int weight = weights[i - 1];
        int value = values[i - 1];

        for (int w = 0; w <= capacity; w++) {
            if (weight > w) {
                dp[i][w] = dp[i - 1][w]; // can't fit item i, so skip it
            } else {
                dp[i][w] = Math.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 array, 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.

public int longestCommonSubsequence(String a, String b) {
    int n = a.length();
    int m = b.length();
    int[][] dp = new int[n + 1][m + 1]; // dp[i][j], row/col 0 default to 0

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // extend the match
            } else {
                dp[i][j] = Math.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 array 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).