DP — From Recursion Up

Hand-copy this into your notebook. Telegraphic by design — every line is derivable from the detailed notes below. Markers (★ ⚠ 💡) sit in the margin so you can box them.

DP = two job types only:
  1. OPTIMIZE  → find min / max value
  2. COUNT     → number of ways to reach a goal

DP = RECURSION (95%) + MEMOIZATION (5%)
  memo = just cache the subproblem's answer, reuse it
  effect: time drops exponential → polynomial

1PARAMETERS   → what describes a subproblem?
2BASE CASE    → "what if it doesn't exist?" (smallest input)
3OPTIONS      → at this index: pick / skip (recurse on each)
4COMBINE+CACHE→ count→SUM | optimize→MIN/MAX ; store; return

#changing params → array dimension
  1 changing  → 1-D dp[]
  2 changing  → 2-D dp[][]
  3 changing  → 3-D / HashMap
constants (array itself, n) do NOT count
HashMap key = concat changing params  e.g. i + "," + j
init dp = -1  → "-1 means not computed yet"

PICK item  → consume capacity/target, add value
SKIP item  → move index, leave capacity
combine = SUM (count) / MAX / MIN (optimize)
guard: if item > remaining → SKIP only (1 option)

★TRICK   stop chasing "winding/unwinding". Trust the
        function: right base + right recurse = right answer.
★TRICK   #changing-params decides 1D/2D/3D. Done.
⚠PITFALL item > target → DON'T return 0. SKIP it.
⚠PITFALL House robber: also dp[i]=max(dp[i], nums[i])
        for all-negative arrays.
⚠PITFALL base: use i==0 (size can't be <0), keep it simple.
💡TIP     LIS prevIdx+1 shifts the -1 sentinel into a
        valid array index.
💡TIP     Greedy = brute force (best-right-now). DP =
        explore ALL options, then min/max. Different beasts.

You're in an interview. The question is "count the ways a child can climb n stairs taking 1, 2, or 3 steps." You write the obvious recursion, it works for n = 5, and then the interviewer says "now n is 40." Your code crawls. The same f(37) is being recomputed thousands of times across different branches, each from scratch. That single wasted recomputation is the entire reason dynamic programming exists — and fixing it is, genuinely, about five lines of code.

The whole thesis here is that DP is not a scary new technique. It's the recursion you already know, with a notepad bolted on. Once you believe that, every problem below becomes a fill-in-the-blanks exercise on one template. We'll build that template first, then run it ten times.

What dynamic programming actually is#

Plain English first: dynamic programming is a way of solving a big problem by solving smaller versions of the same problem and remembering the answers so you never solve the same small version twice. The "remembering" is the only thing that separates it from plain recursion.

Here's a sharp filter for when a problem is a DP problem. DP solves exactly two kinds of question:

The four-step template the whole course in one box#

Definition: every DP solution in this session is the same four moves. Memorize this and you stop "thinking about DP" entirely — you just fill in the blanks.

1. Parameters. Ask what uniquely describes one subproblem. Some parameters are constant (the input array, its size n); some change on each call (an index, a remaining sum). Only the changing ones matter.
2. Base case. A useful trick: ask "what's the smallest/empty version, and what's its answer?" Keep it dead simple.
3. Options. Standing at the current element, enumerate your choices — almost always pick it or skip it — and make a recursive call for each.
4. Combine + cache. If counting, sum the option results; if optimizing, take min or max. Store the answer in your memo, then return it.

Two ways to write it: top-down and bottom-up#

Definition: the same DP can be coded two ways. Top-down = recursion that starts at the goal and dives toward the base, caching as it returns. Bottom-up = a loop that starts at the base case and fills a table upward until it reaches the goal.

Choosing the memo: how many dimensions?#

The single most useful trick in the session. Beginners freeze on "should this be a 1-D, 2-D, or 3-D array?" The answer: count the parameters that change on each recursive call. That count is your number of dimensions.

For a HashMap, build the key by concatenating the changing parameters: String key = i + "," + j;. Because those values are unique per subproblem, the key is unique. Constants like the array and its length never count toward the dimension — they don't change, so they can't distinguish subproblems.

The ten problems — same template, every time

Each problem below follows the identical rhythm: plain-English statement → the four template steps → the code the class arrived at. Notice you're never inventing a new technique — you're choosing parameters and an option set.

Problem 1 — Coin change, count the ways COUNT#

Plain English: given coin denominations and a target sum, how many different combinations add up to the target? You have an infinite supply of each coin. For coins = {1,2,3}, sum = 4 the answer is 4: {1,1,1,1}, {1,1,2}, {2,2}, {1,3}.

Template applied#

• Parameters (changing): remaining sum and coin index n → two changing → 2-D memo.
• Base cases: sum == 0 → return 1 (one valid way found); n == 0 (no coins left) → return 0.
• Options: if this coin fits (a[n-1] ≤ sum): pick it — stay on the same index (infinite supply!) and reduce the sum — plus skip it — move to the previous coin, sum unchanged.
• Combine: it's a counting problem, so add the two option results.

int coinChange(int[] a, int sum, int n, int[][] dp) {
  // base cases
  if (sum == 0) return dp[n][sum] = 1;   // found a way
  if (n == 0)   return 0;                 // no coins left
  if (dp[n][sum] != -1) return dp[n][sum]; // memo hit

  if (a[n-1] <= sum)
    // PICK (same n, infinite supply) + SKIP (n-1)
    return dp[n][sum] = coinChange(a, sum - a[n-1], n, dp) + coinChange(a, sum, n - 1, dp);
  else
    // coin too big — no choice but to skip it
    return dp[n][sum] = coinChange(a, sum, n - 1, dp);
}

Time O(N×sum) · Space O(N×sum)

Problem 2 — Climbing stairs (1, 2, or 3 at a time) COUNT#

Plain English: a child climbs n stairs, hopping 1, 2, or 3 steps at a time. How many distinct ways to reach the top? For n = 3 the answer is 4: 1+1+1, 1+2, 2+1, 3.

Template applied#

• Parameter (changing): just n, the steps remaining → one changing → 1-D memo.
• Base cases: n == 0 → return 1 (reached the top exactly — one valid path); n < 0 → return 0 (overshot).
• Options: three of them — recurse on n-1, n-2, n-3.
• Combine: counting → add all three.

int climb(int n, int[] dp) {
  if (n == 0) return 1;          // reached top exactly
  if (n < 0)  return 0;          // overshot
  if (dp[n] != -1) return dp[n];  // memo hit
  return dp[n] = climb(n-1, dp) + climb(n-2, dp) + climb(n-3, dp);
}

Time O(n) · Space O(n)

Problem 3 — Max sum of non-adjacent elements (House Robber) OPTIMIZE#

Plain English: pick a subset of array elements with the maximum sum, but you may never pick two adjacent elements. For {1,2,9,4,5,0,4,11,6} the best is {1,9,5,11} = 26.

Template applied#

• Parameter (changing): index i → 1-D.
• Options: pick element i → add nums[i] and jump to i-2 (skip the neighbor); skip → move to i-1.
• Combine: optimizing → take the max.

// bottom-up: lookup[i] = best non-adjacent sum up to index i
int robber(int[] nums) {
  int n = nums.length;
  if (n == 0) return 0;
  if (n == 1) return nums[0];
  int[] lookup = new int[n];
  lookup[0] = nums[0];
  lookup[1] = Math.max(nums[0], nums[1]);
  for (int i = 2; i < n; i++) {
    lookup[i] = Math.max(lookup[i-1], lookup[i-2] + nums[i]); // skip vs pick
    lookup[i] = Math.max(lookup[i], nums[i]);                 // all-negative guard
  }
  return lookup[n-1];
}

Time O(n) · Space O(n)

Problem 4 — Minimum deletions to make a palindrome OPTIMIZE#

Plain English: delete the fewest characters so the remaining string reads the same forwards and backwards. "ACBCDBAA" needs 3 deletions.

Template applied#

• Parameters (changing): start index i and end index j → two changing → 2-D memo (or HashMap keyed i+"|"+j). The string and its length are constants.
• Base case: i ≥ j (pointers met or crossed) → return 0.
• Options: if s[i] == s[j], no deletion needed — recurse on (i+1, j-1). Otherwise you must delete one end: 1 + min( delete-last (i, j-1), delete-first (i+1, j) ).

int minDeletions(String x, int i, int j, Map<String,Integer> memo) {
  if (i >= j) return 0;                 // 0 or 1 char left
  String key = i + "|" + j;
  if (memo.containsKey(key)) return memo.get(key);

  int ans;
  if (x.charAt(i) == x.charAt(j))
    ans = minDeletions(x, i+1, j-1, memo);   // ends match, free
  else
    ans = 1 + Math.min(minDeletions(x, i, j-1, memo),    // drop last
    minDeletions(x, i+1, j, memo));   // drop first
  memo.put(key, ans);
  return ans;
}

Problem 5 — 0/1 Knapsack OPTIMIZE#

Plain English: you have items, each with a weight and a value, and a bag that holds at most weight W. Maximize total value without exceeding the capacity. Each item is taken whole or not at all ("0/1").

Template applied#

• Parameters (changing): remaining capacity W and item index n → 2-D. One index serves both the value and weight arrays.
• Base case: n == 0 or W == 0 → return 0.
• Options: if the item is too heavy (wt[n-1] > W) you can only skip. Otherwise choose the max of: take — add val[n-1], reduce capacity by wt[n-1], move to n-1 — vs skip — move to n-1, capacity unchanged.

int knapSack(int W, int[] wt, int[] val, int n, int[][] dp) {
  if (n == 0 || W == 0) return 0;
  if (dp[n][W] != -1) return dp[n][W];
  if (wt[n-1] > W)                          // too heavy → must skip
    return dp[n][W] = knapSack(W, wt, val, n-1, dp);
  return dp[n][W] = Math.max(val[n-1] + knapSack(W - wt[n-1], wt, val, n-1, dp), // take
    knapSack(W, wt, val, n-1, dp));                     // skip
}

Time O(N×W) · Space O(N×W)

Problem 6 — Subset sum (does one exist?) DECISION #

Plain English: given non-negative integers and a target, is there any subset that adds up exactly to the target? {3,34,4,12,5,2}, target 9 → true (4+5). Target 30 → false.

Template applied#

• Parameters (changing): remaining sum and index n → 2-D. Each element used at most once (no infinite supply).
• Base cases: sum == 0 → true (1); n ≤ 0 → false (0).
• Options: if a[n-1] > sum you must exclude. Otherwise it's an OR of include (sum - a[n-1], index n-1) and exclude (sum, index n-1).
• Combine: a decision problem — logical OR (true if either branch succeeds).

int subsetSum(int[] a, int n, int sum, int[][] tab) {
  if (sum == 0) return 1;          // found target
  if (n <= 0)   return 0;          // out of elements
  if (tab[n-1][sum] != -1) return tab[n-1][sum];
  if (a[n-1] > sum)                  // can't include
    return tab[n-1][sum] = subsetSum(a, n-1, sum, tab);
  // include OR exclude
  boolean ok = subsetSum(a, n-1, sum, tab) != 0 || subsetSum(a, n-1, sum - a[n-1], tab) != 0;
  return tab[n-1][sum] = ok ? 1 : 0;
}

Time O(N×sum) · Space O(N×sum)

Problem 7 — Minimum subset-sum difference OPTIMIZE#

Plain English: split a set into two groups so the difference between their sums is as small as possible; return that minimum difference. {10,20,15,5,25} splits into sums 35 and 40 → difference 5.

Template applied#

• Parameters (changing): index n and S1 (sum collected in group 1) → 2-D. You don't need S2 separately — it's totalSum − S1.
• Base case: n < 0 → return |S1 − S2|.
• Options: put the current element in group 1 (S1 + a[n]) or group 2 (S2 + a[n]).
• Combine: take the min of the two resulting differences.

int minDiff(int[] S, int n, int s1, int s2, Map<String,Integer> memo) {
  if (n < 0) return Math.abs(s1 - s2);
  String key = n + "|" + s1;          // s2 is implied
  if (memo.containsKey(key)) return memo.get(key);
  int inc = minDiff(S, n-1, s1 + S[n], s2, memo);   // → group 1
  int exc = minDiff(S, n-1, s1, s2 + S[n], memo);   // → group 2
  int ans = Math.min(inc, exc);
  memo.put(key, ans);
  return ans;
}

Time O(N×sum) · Space O(N×sum)

Problem 8 — Longest increasing subsequence (LIS) OPTIMIZE#

Plain English: find the length of the longest subsequence whose elements are in strictly increasing order. {3,10,2,1,20} → {3,10,20}, length 3.

Template applied#

• Parameters (changing): current index idx and prevIdx (the index of the last element kept) → 2-D.
• Base case: idx == n → return 0 (nothing left to extend).
• Options: skip the current element (idx+1, same prevIdx); or, only if prevIdx == -1 or a[idx] > a[prevIdx], take it (1 + f(idx+1, idx)).
• Combine: max of take and skip.

int f(int idx, int prevIdx, int n, int[] a, int[][] dp) {
  if (idx == n) return 0;
  if (dp[idx][prevIdx + 1] != -1) return dp[idx][prevIdx + 1];
  int skip = f(idx + 1, prevIdx, n, a, dp);
  int take = Integer.MIN_VALUE;
  if (prevIdx == -1 || a[idx] > a[prevIdx])
    take = 1 + f(idx + 1, idx, n, a, dp);   // current becomes new prev
  return dp[idx][prevIdx + 1] = Math.max(take, skip);
}

Time O(n²) · Space O(n²)

Problem 9 — Decode ways (digits → letters) COUNT#

Plain English: with mapping 1→A, 2→B, … 26→Z, count how many ways a digit string can be decoded. "123" → 3 (ABC, AW, LC); "1221" → 5.

Template applied (bottom-up)#

• Parameter (changing): position i in the string → 1-D table T where T[i] = ways to decode the first i characters.
• Base case: T[0] = 1 (empty string, one way) and T[1] = 1.
• Options at each i: if the single digit > 0, it decodes alone → add T[i-1]. If the previous two digits form 10–26, that pair decodes too → add T[i-2].
• Combine: counting → sum the valid one-digit and two-digit contributions.

int count(int x) {
  String seq = String.valueOf(x);
  int[] T = new int[seq.length() + 1];
  T[0] = 1; T[1] = 1;
  for (int i = 2; i <= seq.length(); i++) {
    if (seq.charAt(i-1) > '0')                 // single digit 1–9
        T[i] = T[i-1];
    if (seq.charAt(i-2) == '1' ||              // two-digit 10–26
        (seq.charAt(i-2) == '2' && seq.charAt(i-1) <= '6')) T[i] += T[i-2];
  }
  return T[seq.length()];
}

Time O(n) · Space O(n)

Problem 10 — Longest increasing path in a matrix OPTIMIZE#

Plain English: in an n×n grid of distinct numbers, find the longest path where each step moves to an adjacent cell (up/down/left/right) whose value is exactly one greater. The path 6→7→8→9 gives length 4.

Template applied (DFS + memo)#

• Parameters (changing): cell coordinates (i, j) → HashMap keyed "i,j" (effectively 2-D). The matrix is constant.
• Base case: a cell always contributes at least length 1 (itself).
• Options: try all 4 directions; recurse only into a neighbor whose value is current + 1 and within bounds.
• Combine: max over the four directions; cache and return.

int dfs(int[][] m, int i, int j, Map<String,Integer> memo) {
  String key = i + "," + j;
  if (memo.containsKey(key)) return memo.get(key);
  int best = 1;                              // the cell itself
  int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
  for (int[] d : dirs) {
    int r = i + d[0], c = j + d[1];
    if (r >= 0 && r < m.length && c >= 0 && c < m.length && m[r][c] - m[i][j] == 1)            // the extra rule
        best = Math.max(best, 1 + dfs(m, r, c, memo));
  }
  memo.put(key, best);
  return best;
}

The follow-ups this material naturally invites. Each answer is short enough to say out loud. Click to expand.