Climbing Stairs — recursion → memo → tabulation

Recognize it from

“Number of ways to climb n stairs taking 1 or 2 steps.” Same shape: decode a digit string (one digit or two), tile a 2×n board with 1×2 and 2×1. The clue is ways add, not “max score.”

What it actually does

The last step onto stair n is either a single step from n−1 or a double step from n−2. Those two groups of paths are disjoint, so ways(n) = ways(n−1) + ways(n−2). That is Fibonacci with ways(1)=1, ways(2)=2.

Plain recursion recomputes the same smaller stair over and over — look at climb(2) in Example 1. Memo stores each n once. Tabulation fills 1, 2, 3, … in order. After that you only need two rolling integers, because the recurrence looks two cells back.

public int climbStairs(int n) {
    int[] memo = new int[n + 1];
    return climb(n, memo);
}
private int climb(int n, int[] memo) {
    if (n <= 2) return n; // n=1 → one single step; n=2 → 1+1 or 2
    if (memo[n] != 0) return memo[n]; // climb(2) is asked from both climb(4) and climb(3)
    memo[n] = climb(n - 1, memo) + climb(n - 2, memo); // last step was a 1 or a 2 — ways add
    return memo[n];
}

public int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1; // ways(1)
    int prev1 = 2; // ways(2)
    for (int i = 3; i <= n; i++) {
        int cur = prev1 + prev2; // only the last two stairs matter
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Example 1 — simple

n = 4. Naive recursion (no memo) so you can see the overlap. Five layouts: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.

Answer: 5 ways. With memo, the second climb(2) would read memo[2] and skip the base case.

Example 2 — every step

n = 5, interview rolling variables. Start prev2 = ways(1) = 1, prev1 = ways(2) = 2. Every i from 3 through 5:

Answer: 8. The eight layouts of five stairs with 1s and 2s. A memo array would hold the same numbers in cells 1…5; the two variables are that array with the old cells thrown away.

House Robber — 1D skip / take, then the circle

Recognize it from

“Maximum money / points, cannot take two adjacent.” Linear street, then the follow-up: houses stand in a circle so the first and last are neighbors. Not House Robber on a tree (that is a different recurrence on left/right children).

What it actually does

At house i you either skip it and keep the best of i−1, or take it and add the best of i−2. Those are the only two legal endings. A dp array makes that visible; two rolling integers are the same pair of cells.

On a circle, taking house 0 forbids house n−1. You cannot encode that with one linear pass. Run the linear robber on [0 .. n−2] (drop the last) and on [1 .. n−1] (drop the first), then take the max. n = 1 is a special case: both ranges would be empty if you are not careful.

public int rob(int[] a) {
    int n = a.length;
    if (n == 0) return 0;
    if (n == 1) return a[0];
    int[] dp = new int[n];
    dp[0] = a[0];
    dp[1] = Math.max(a[0], a[1]); // two houses: take the richer one
    for (int i = 2; i < n; i++) {
        int skip = dp[i - 1]; // leave a[i] on the table
        int take = dp[i - 2] + a[i]; // a[i-1] is then forbidden
        dp[i] = Math.max(skip, take);
    }
    return dp[n - 1];
}

public int rob(int[] a) {
    int n = a.length;
    if (n == 0) return 0;
    if (n == 1) return a[0]; // a one-house circle is just that house
    return Math.max(robLine(a, 0, n - 2), robLine(a, 1, n - 1));
}
private int robLine(int[] a, int lo, int hi) {
    int prev2 = 0, prev1 = 0; // best ending two back, one back
    for (int i = lo; i <= hi; i++) {
        int cur = Math.max(prev1, prev2 + a[i]);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Example 1 — simple

Linear street [1, 2, 3, 1]. Best is house 0 + house 2 = 4 (the two 1s at the ends are not adjacent on a line).

Answer: 4.

Example 2 — every step

Circle [2, 3, 2]. Taking both ends is 2+2 = 4 — illegal, because index 0 and index 2 touch. Run both linear ranges. n = 3, ranges are [0..1] and [1..2].

Answer: max(3, 3) = 3 — the middle house. The illegal 4 never appears in either range, because each range dropped one end.

Unique Paths / grid DP — right and down on a DAG

Recognize it from

“Start cell to end cell, only right and down (maybe left/up forbidden), count paths or max score, skip traps.” Obstacles as 1 or −1. Follow-up is often max reward on the same DAG. Four-direction increasing path is not this — that needs memo DFS.

What it actually does

Right and down only means every cell has at most two parents: above and left. The graph is a DAG, so a table in row-major order is a valid topological fill. Path count adds the two parents. Path value takes max or min, then adds this cell. Do not reuse a count table as if it were a score.

A rolling 1D array is the previous row. When you visit column j you overwrite it; read “up” before the write, and “left” from dp[j−1] which is already this row. An obstacle must be written as 0 (count) or a sentinel (max), or the next cell will add a stale number that walked through the block.

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1; // only down the first column
    for (int j = 0; j < n; j++) dp[0][j] = 1; // only right along the first row
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // ways add from above and left
        }
    }
    return dp[m - 1][n - 1];
}

public int uniquePathsWithObstacles(int[][] g) {
    int m = g.length, n = g[0].length;
    int[] dp = new int[n]; // dp[j] is "this column, previous row" until we overwrite
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1) {
                dp[j] = 0; // blocked: contributes no paths; must clear a stale up-count
                continue;
            }
            if (i == 0 && j == 0) {
                dp[0] = 1;
                continue;
            }
            int up = i > 0 ? dp[j] : 0; // still the previous row at column j
            int left = j > 0 ? dp[j - 1] : 0; // already this row
            dp[j] = up + left;
        }
    }
    return dp[n - 1];
}

Example 1 — simple

Empty 2×3 grid. Three paths: right-right-down, right-down-right, down-right-right.

Answer: 3 paths.

Example 2 — every step

3×3 with one obstacle at the center (1,1). Count paths, obstacle = 1. Every cell:

Answer: 2. The four paths that would have stepped on the center die. Max-reward on the same grid is a different recurrence: grid[i][j] + max(up, left), still skipping the zeroed cell — see the notebook max-reward cards, not this count.

0/1 knapsack / partition — boolean subset sum

Recognize it from

“Can you pick a subset that sums to T?” Partition equal subset sum is T = total/2. Target-sum with +/− signs is the same boolean after algebra. If they want the actual subset, keep parent pointers or backtrack when n is tiny — the boolean table only answers yes/no.

What it actually does

Each number may be used at most once. After considering the first i items, dp[i][w] is whether sum w is possible. Transition: skip the item (copy the previous row) or take it if w ≥ x and dp[i−1][w−x] was already true. That previous-row read is what makes it 0/1 rather than unbounded.

The 1D roll overwrites the same array. Looping capacity downward means dp[w−x] still belongs to the previous item. Looping upward lets this same item satisfy dp[w−x] and then immediately satisfy dp[w] — using x twice. Example 2 is that bug.

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if (sum % 2 != 0) return false; // odd total cannot split in half
    int T = sum / 2;
    int n = nums.length;
    boolean[][] dp = new boolean[n + 1][T + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = true; // sum 0: take nothing
    for (int i = 1; i <= n; i++) {
        int x = nums[i - 1];
        for (int w = 1; w <= T; w++) {
            dp[i][w] = dp[i - 1][w]; // skip this item
            if (w >= x) dp[i][w] = dp[i][w] || dp[i - 1][w - x]; // 0/1: previous row only
        }
    }
    return dp[n][T];
}

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int x : nums) sum += x;
    if ((sum & 1) != 0) return false;
    int T = sum / 2;
    boolean[] dp = new boolean[T + 1];
    dp[0] = true;
    for (int x : nums) {
        for (int w = T; w >= x; w--) { // reverse: dp[w-x] is still "without this x"
            dp[w] = dp[w] || dp[w - x];
        }
    }
    return dp[T];
}

Example 1 — simple

nums = [1, 5, 11, 5], total 22, target T = 11. Two yes subsets: {11} and {1,5,5}.

Answer: true — dp[11] is set after the 11, and stays set.

Example 2 — every step

Why capacity must go down. One item of value 5, capacity 10. 0/1 can make 0 or 5, never 10. Upward reuses the 5.

Answer of the bug: dp[10] = true even though you owned only one 5. That is unbounded knapsack. 0/1 must not see a write from the same item. On [1,5,11,5] the same upward pass after the first 5 would mark 10 before the second 5 ever runs.

LCS — two strings, three table moves

Recognize it from

“Longest common subsequence (not substring).” Letters may skip. Related speak: shortest common supersequence = n+m−LCS; delete-only distance = n+m−2·LCS. If they allow replace as well, that is edit distance — a third transition, not max of two.

What it actually does

A subsequence keeps order and may drop letters. dp[i][j] is the LCS of the first i letters of s and the first j of t. Empty prefix is 0, which is why the table is (m+1)×(n+1).

Three moves, only two of which fire on a given cell: if the current letters match, you must take the diagonal + 1 (keeping both letters is never worse than dropping one). If they differ, you drop one letter or the other and take the max. There is no “replace” in LCS. Edit distance adds a third option: cost 1 from the diagonal on a mismatch.

public int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1]; // extra row/col of zeros for empty prefixes
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

public int longestCommonSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // take the match; skip the letters in between
            } else {
                int skipS = dp[i - 1][j]; // drop s[i-1], keep t's prefix
                int skipT = dp[i][j - 1]; // drop t[j-1], keep s's prefix
                dp[i][j] = Math.max(skipS, skipT); // cannot take a mismatch into the subsequence
            }
        }
    }
    return dp[m][n];
}

Example 1 — simple

s = "ace", t = "abcde". The whole of s sits inside t.

Answer: 3 — ace.

Example 2 — every step

s = "ABCD", t = "ACBD" (length 4). Every cell of the 4×4 interior. LCS length 3 (e.g. ABD or ACD).

Answer: 3.

See also — same notebook cards, different recurrence

Grid count and grid max-reward share a DAG and different operators (add vs max). House Robber II is the circle split, not Kadane circular. Longest increasing path is memo DFS. Partition that must return the subset is this knapsack plus reconstruction, or the backtracking chapter when n is small.