Pattern 14: Dynamic Programming (Memoization vs. Tabulation)

0. The Template (Copy-Paste Skeleton)

Two skeletons — top-down memo and bottom-up table. Write the recurrence first, in English, before you touch either.

// TEMPLATE A — TOP-DOWN (recursion + memo). Write this FIRST: it's just brute force + a cache.
Integer[] memo;                                   // Integer, so null means "not computed"

int dp(int i, int[] nums) {
    if (i < 0) return 0;                          // 1. BASE CASE
    if (memo[i] != null) return memo[i];          // 2. CACHE HIT

    int take = nums[i] + dp(i - 2, nums);         // 3. TRY EVERY CHOICE
    int skip = dp(i - 1, nums);

    return memo[i] = Math.max(take, skip);        // 4. STORE and return
}

// TEMPLATE B — BOTTOM-UP (iterative table). Convert from A once the recurrence is proven.
int solve(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n + 1];
    dp[0] = 0;  dp[1] = nums[0];                  // BASE CASES — the usual bug source

    for (int i = 2; i <= n; i++) {                // ORDER: every dependency already computed
        dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
    }
    return dp[n];
}

// TEMPLATE C — SPACE OPTIMISATION: if dp[i] only reads dp[i-1] and dp[i-2], keep 2 variables
int prev2 = 0, prev1 = nums[0];
for (int i = 1; i < nums.length; i++) {
    int cur = Math.max(prev1, nums[i] + prev2);
    prev2 = prev1;  prev1 = cur;
}
return prev1;                                     // O(n) time, O(1) space

// TEMPLATE D — 2-D DP (two sequences / knapsack)
int[][] dp = new int[m + 1][n + 1];               // +1 row/col for the empty-prefix base case
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        dp[i][j] = (a[i-1] == b[j-1])
            ? dp[i-1][j-1] + 1                    // match → extend the diagonal
            : Math.max(dp[i-1][j], dp[i][j-1]);   // no match → best of dropping one char
return dp[m][n];

The 5-step method — follow it in this order, every time

1. State: what does dp[i] mean? Say it as an English sentence. (“the max money robbable from the first i houses”). If you can’t say it, you can’t code it.
2. Recurrence: how does dp[i] follow from smaller states? This is the whole problem.
3. Base case: the smallest input, usually dp[0]. Half of all DP bugs live here.
4. Order: iterate so every dependency is already filled in.
5. Answer: is it dp[n], dp[n][m], or max(dp[...])? Not always the last cell.

Pattern → recurrence lookup

Family	State	Recurrence
0/1 Knapsack	dp[i][w] = best using first i items, capacity w	max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
Unbounded knapsack / coin change	dp[amount]	min(dp[a], dp[a - coin] + 1) — inner loop over coins, not i-1
Fibonacci-style (stairs, house robber)	dp[i]	f(dp[i-1], dp[i-2])
LCS / edit distance	dp[i][j] over two strings	match → dp[i-1][j-1] (+1); else best of the neighbours
LIS	dp[i] = longest ending at i	max(dp[j]) + 1 for all j < i with a[j] < a[i] — O(n²), or patience sort for O(n log n)
Palindromic substrings	dp[i][j] = is s[i..j] a palindrome	s[i]==s[j] && dp[i+1][j-1] — iterate i descending
Grid paths	dp[r][c]	dp[r-1][c] + dp[r][c-1]

Debugging your DP thinking

• Stuck on the recurrence? Write the brute-force recursion first (Template A without the memo), confirm it’s correct on a tiny input, then add the cache. Memoisation never changes the answer, only the speed.
• Wrong answer? Print the table and hand-check the first two rows. It’s almost always a base case or a loop bound.
• Getting dp[i] from dp[i+1]? Your iteration direction is backwards — flip the loop.

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• “Maximize / Minimize” a value under constraints
• “How many ways” to reach a goal
• “Can you reach / achieve” something (yes/no feasibility)
• Problem has optimal substructure (big problem = combining smaller subproblems)
• Problem has overlapping subproblems (same subproblem solved multiple times)

Two Properties Required for DP

1. Optimal Substructure: The optimal solution contains optimal solutions to subproblems
2. Overlapping Subproblems: Recursive tree recalculates the same states (e.g., Fibonacci calculates f(3) multiple times)

The Workflow (3-Step Mindset)

Step 1: Write the RECURSIVE solution (forget efficiency, just get it correct)
Step 2: MEMOIZE (Top-Down) - add a cache to store results of recursive calls
Step 3: TABULATE (Bottom-Up) - convert recursion into a loop filling a table

The ‘Trick’ to Know

• State definition is everything. Ask yourself: “What variables uniquely define where I am in the problem?” That’s your DP state.
• Transition = the recurrence relation. It’s the max() or min() formula connecting current state to previous states.
• Base case = the smallest subproblem you can solve without recursion (e.g., 0 items, 0 capacity, empty string).

---

2. The 5 Core DP Patterns

Pattern A: 0/1 Knapsack

• Sign: “Pick or Don’t Pick” - binary choice for each element
• State: dp[i][w] = best value using first i items with capacity w
• Transition: dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-wt[i]])
• Examples: Partition Equal Subset Sum, Target Sum

Pattern B: Unbounded Knapsack

• Sign: “How many ways to make X” or “Minimum items to reach X” (can reuse items)
• State: dp[w] = min coins / max ways for capacity w
• Transition: dp[w] = min(dp[w], 1 + dp[w - coin]) for each coin
• Examples: Coin Change, Rod Cutting

Pattern C: Longest Common Subsequence (LCS)

• Sign: Two strings, looking for max length or edit distance
• State: dp[i][j] = answer for first i chars of string1 and first j chars of string2
• Transition: If s1[i] == s2[j]: dp[i][j] = 1 + dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1])
• Examples: Longest Palindromic Subsequence, Edit Distance

Pattern D: Fibonacci / Linear DP

• Sign: “How many ways to reach step N?” - answer depends on 1-2 previous steps
• State: dp[i] = answer at position i
• Transition: dp[i] = dp[i-1] + dp[i-2] (or similar)
• Examples: Climbing Stairs, House Robber, Decode Ways

Pattern E: Grid / Matrix Path

• Sign: “Minimum path sum” or “Number of paths” in a 2D grid
• State: dp[i][j] = answer at cell (i, j)
• Transition: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
• Examples: Unique Paths, Minimum Path Sum, Cherry Pickup

---

3. Java Implementation

0/1 Knapsack (Bottom-Up)

public class Knapsack {
    public static int solve(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= capacity; w++) {
                dp[i][w] = dp[i - 1][w]; // exclude item i

                if (weights[i - 1] <= w) {
                    int include = values[i - 1] + dp[i - 1][w - weights[i - 1]];
                    dp[i][w] = Math.max(dp[i][w], include);
                }
            }
        }

        return dp[n][capacity];
    }
}

House Robber (Space-Optimized Linear DP)

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        int prev2 = 0; // dp[i-2]
        int prev1 = 0; // dp[i-1]

        for (int num : nums) {
            int current = Math.max(prev1, num + prev2);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

House Robber II (Circular)

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];

        // Can't rob both first and last → solve two sub-problems
        return Math.max(
            robRange(nums, 0, nums.length - 2),
            robRange(nums, 1, nums.length - 1)
        );
    }

    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;

        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, nums[i] + prev2);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Java Architecture Insights

• Space optimization: For 1D DP where dp[i] only depends on dp[i-1] and dp[i-2], replace the array with two variables → O(1) space.
• For 2D DP: If each row only depends on the previous row, use a 1D array and overwrite in-place (iterate backwards for 0/1 Knapsack to avoid using updated values).
• int[][] vs Integer[][]: Primitive arrays are much faster. Only use Integer[][] for memoization where you need null to distinguish “not computed” from “computed as 0”.

---

4. Mental Model & Visualization

Knapsack DP Table (weights=[3,2,4], values=[150,100,200], capacity=4)

          Capacity →  0    1    2    3    4
Items ↓
0 (none)              0    0    0    0    0
A (3kg, $150)         0    0    0  150  150
B (2kg, $100)         0    0  100  150  250
C (4kg, $200)         0    0  100  150  250

dp[2][4]: max(dp[1][4], 100 + dp[1][2]) = max(150, 100+0) = 150
Wait — with all 3 items: dp[3][4] = max(dp[2][4], 200+dp[2][0]) = max(250, 200) = 250

House Robber Table (houses = [2, 7, 9, 3, 1])

House:    0   1   2   3   4
Money:    2   7   9   3   1
DP:       2   7  11  11  12

dp[4] = max(dp[3], 1 + dp[2]) = max(11, 1+11) = 12

Senior Mental Trigger

“Maximize/minimize with constraints + overlapping subproblems = DP. Define the state, find the transition, start from base case.”

---

5. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty	Pattern
LC 70	Climbing Stairs	Easy	Fibonacci
LC 198	House Robber	Medium	Linear
LC 322	Coin Change	Medium	Unbounded
LC 62	Unique Paths	Medium	Grid
LC 300	Longest Increasing Subsequence	Medium	LIS

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty	Pattern
LC 416	Partition Equal Subset Sum	Medium	0/1 Knap
LC 1143	Longest Common Subsequence	Medium	LCS
LC 72	Edit Distance	Medium	LCS
LC 312	Burst Balloons	Hard	Interval
LC 139	Word Break	Medium	Linear
LC 10	Regular Expression Matching	Hard	2D DP

---

6. Time & Space Complexity Table

Pattern	Time	Space (naive)	Space (optimized)
Fibonacci/Linear	O(n)	O(n)	O(1)
0/1 Knapsack	O(n * W)	O(n * W)	O(W)
Unbounded Knap	O(n * W)	O(W)	O(W)
LCS / 2D	O(m * n)	O(m * n)	O(min(m, n))
Grid Path	O(m * n)	O(m * n)	O(n)

---

7. How to Debug Your DP Thinking

When stuck on a new DP problem, ask:

1. What is the “State”? (In Knapsack: item index + remaining weight)
2. What is the “Base Case”? (Capacity 0 or no items → value 0)
3. What is the “Transition”? (The max()/min() formula connecting states)