Dynamic Programming Notes — Interview Cheat Sheet

One-stop reference for DP: when to use, how to think, all major patterns
(linear, grid, knapsack, subsequence, interval, partition, tree, bitmask,
digit, state-machine, game-theory), templates, complexity, and decision tree.

---

0) Five Questions to Ask First

Your answers pick the pattern.

1. Optimal substructure? Can the answer be built from answers to smaller subproblems?
2. Overlapping subproblems? Does naive recursion recompute the same thing?
3. What is the state? What variables uniquely identify a subproblem?
4. What are the choices at each state? (take/skip, pick coin, partition, etc.)
5. What is the base case + final answer location?

If "yes" to 1 & 2 → DP. Otherwise consider greedy / divide & conquer / backtracking.

---

1) DP vs Other Paradigms

Pattern	Use when
Greedy	Locally optimal choice always leads to global optimum (Activity Selection, Huffman)
Divide & Conquer	Subproblems are independent (Merge Sort, Quick Sort)
Backtracking	Need all solutions / constraint satisfaction (N-Queens, Sudoku)
DP	Overlapping subproblems + optimal substructure (count/min/max/yes-no)
DP + Bitmask	Small N (≤ ~20) with subset state
DP on graph / tree	Dependency between subproblems given by graph/tree edges

---

2) Three Forms of DP

A) Recursion (brute force)

• Direct translation of recurrence. Exponential time. Useful to derive the recurrence.

B) Top-Down (Memoization)

• Recursion + cache. Computes only needed states.
• Pros: matches recursion intuition, easy on tree/graph DPs.
• Cons: recursion stack overhead.

C) Bottom-Up (Tabulation)

• Iterative; fill table in dependency order.
• Pros: no recursion, easier to space-optimize.
• Cons: must know iteration order; sometimes unnatural.

	Top-Down	Bottom-Up
Style	Recursive + memo	Iterative table
Stack risk	Yes (deep recursion)	No
Easy to space-optimize	❌	✅
Best for graph/tree DP	✅	Often awkward
Best for linear/grid	OK	✅

Rule of thumb: start top-down to derive recurrence → convert to bottom-up → space-optimize.

---

3) Universal DP Recipe

1. Define state: dp[i], dp[i][j], dp[i][cap], dp[mask][i] …
2. Define meaning: e.g., "min cost to reach i", "ways to make sum j using first i items".
3. Write recurrence from the choices at state.
4. Base cases.
5. Iteration order (bottom-up): each state depends only on already-filled states.
6. Final answer: which cell holds it?
7. Space optimize if only previous row/col needed.

---

4) Master Decision Guide (Pattern Picker)

Problem flavor	Pattern
Steps with 1 / 2 / k jump options	Linear 1D (Fibonacci-style)
Pick non-adjacent for max sum	House Robber
Min/max path in grid	Grid 2D
"Pick items, capacity W, max value"	0/1 Knapsack
"Unlimited supply, min coins / ways"	Unbounded Knapsack
"Subset sum / partition equally"	Subset-sum knapsack
LCS / LIS / Edit Distance	Subsequence / String DP
Palindromic substring / subseq	Interval DP / Expand-around
Burst balloons / Matrix Chain Mult	Interval DP (dp[i][j] over range)
Palindrome / word break partitions	Partition DP
Tree path / rob house tree	Tree DP (postorder return tuple)
Shortest/longest path in DAG	DP on DAG (topo + relax)
TSP / assign N tasks to N people	Bitmask DP (N ≤ 20)
Count numbers ≤ N with property	Digit DP
Two-player optimal (Nim-style)	Game Theory DP (minimax)
Stock buy/sell variants	State-Machine DP
Count ways (paths, decodings, dice)	Counting DP
Probability over states	Probability DP

---

5) Pattern 1 — Linear 1D (Fibonacci Family)

State: dp[i] = answer ending at / using first i items.

// Climb Stairs (LC 70)
function climb(n) {
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}
// Time O(n), Space O(1)

Examples: Climbing Stairs, Min Cost Climbing Stairs, House Robber I/II, Decode Ways, Tribonacci, Delete & Earn.

Problem	Recurrence
Climb Stairs	dp[i] = dp[i-1] + dp[i-2]
Min Cost Climbing	dp[i] = min(dp[i-1]+c[i-1], dp[i-2]+c[i-2])
House Robber	dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Decode Ways	dp[i] = dp[i-1] + (valid two-digit ? dp[i-2] : 0)

---

6) Pattern 2 — Grid 2D Paths

State: dp[i][j] = best value reaching cell (i,j).

// Min Path Sum (LC 64)
function minPathSum(g) {
  const m = g.length, n = g[0].length;
  const dp = g.map(r => r.slice());
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const up   = i ? dp[i-1][j] : Infinity;
      const left = j ? dp[i][j-1] : Infinity;
      dp[i][j] += Math.min(up, left);
    }
  return dp[m-1][n-1];
}
// Time O(m*n), Space O(m*n) → can drop to O(n)

Examples: Unique Paths I/II, Min Path Sum, Triangle, Maximal Square, Min Falling Path Sum, Cherry Pickup (3D).

---

7) Pattern 3 — 0/1 Knapsack

Each item taken at most once.

State: dp[i][w] = best value using first i items, capacity w.

function knapsack01(wt, val, W) {
  const n = wt.length;
  const dp = Array.from({length: n+1}, () => new Array(W+1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i-1][w];                              // skip
      if (w >= wt[i-1])
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w-wt[i-1]] + val[i-1]);
    }
  return dp[n][W];
}
// Time O(n*W), Space O(n*W) → 1D rolling: iterate w from W down to wt[i-1]

Variants:
| Variant | Trick |
|---|---|
| Subset Sum | dp[i][s] boolean |
| Partition Equal Subset Sum | Subset sum to total/2 |
| Target Sum | Reduce to subset sum |
| Last Stone Weight II | Subset sum closest to total/2 |
| Count Subsets w/ Sum K | dp[i][s] = dp[i-1][s] + dp[i-1][s-a[i]] |
| Ones and Zeroes | 2-cap knapsack (dp[i][zeros][ones]) |

---

8) Pattern 4 — Unbounded Knapsack

Each item taken unlimited times.

State: dp[i][w] similar; transition uses dp[i][w-wt[i-1]] (same row).

// Coin Change — fewest coins (LC 322)
function coinChange(coins, amt) {
  const dp = new Array(amt+1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amt; a++)
    for (const c of coins)
      if (a >= c) dp[a] = Math.min(dp[a], dp[a-c] + 1);
  return dp[amt] === Infinity ? -1 : dp[amt];
}
// Time O(amt * coins), Space O(amt)

Examples: Coin Change, Coin Change II (count ways), Rod Cutting, Combination Sum IV, Perfect Squares.

Order matters!

• Outer amount, inner coins → counts permutations (Combination Sum IV).
• Outer coins, inner amount → counts unique combinations (Coin Change II).

---

9) Pattern 5 — Subsequence / String DP

State: dp[i][j] over indices of two strings (or one).

// Longest Common Subsequence (LC 1143)
function lcs(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i-1] === b[j-1]
        ? dp[i-1][j-1] + 1
        : Math.max(dp[i-1][j], dp[i][j-1]);
  return dp[m][n];
}
// Time O(m*n), Space O(m*n) → O(min(m,n)) rolling

Problem	Recurrence (match vs mismatch)
LCS	match: 1 + dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1])
Edit Distance	1 + min(insert, delete, replace)
Distinct Subsequences	dp[i-1][j-1] + dp[i-1][j] if match, else dp[i-1][j]
Shortest Common Supersequence	m + n - LCS
Min Insertions for Palindrome	n - LPS(s) where LPS = LCS(s, reverse(s))
Wildcard / Regex matching	match * as 0 or many

LIS (1D state, O(n log n) with binary search)

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const m = (lo + hi) >> 1;
      if (tails[m] < x) lo = m + 1; else hi = m;
    }
    tails[lo] = x;
  }
  return tails.length;
}
// Time O(n log n)

---

10) Pattern 6 — Palindromic DP

Problem	Approach
Longest Palindrome Substring	Expand around center O(n²), or DP dp[i][j]
Longest Palindrome Subseq	LCS(s, reverse(s))
Palindromic Substrings count	Expand around center / DP boolean
Palindrome Partitioning II (min cuts)	DP + palindrome table

// dp[i][j] = is s[i..j] palindrome?
for (let len = 1; len <= n; len++)
  for (let i = 0; i + len - 1 < n; i++) {
    const j = i + len - 1;
    if (s[i] !== s[j]) dp[i][j] = false;
    else dp[i][j] = len <= 2 ? true : dp[i+1][j-1];
  }

---

11) Pattern 7 — Interval DP

State: dp[i][j] = answer over interval [i..j]. Iterate by length.

// Matrix Chain Multiplication template
for (let len = 2; len <= n; len++)
  for (let i = 0; i + len - 1 < n; i++) {
    const j = i + len - 1;
    dp[i][j] = Infinity;
    for (let k = i; k < j; k++)
      dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,k,j));
  }

Examples: Matrix Chain Mult, Burst Balloons, Min Cost Tree from Leaf Values, Stone Game (interval), Strange Printer, Remove Boxes.

• Time often O(n³). Space O(n²).
• Always iterate shorter intervals first.

---

12) Pattern 8 — Partition DP

Split the array/string into pieces minimizing/counting something.

// Word Break (LC 139)
function wordBreak(s, dict) {
  const set = new Set(dict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    for (let j = 0; j < i; j++)
      if (dp[j] && set.has(s.slice(j, i))) { dp[i] = true; break; }
  return dp[s.length];
}

Examples: Word Break I/II, Palindrome Partitioning II, Perfect Squares, Decode Ways.

---

13) Pattern 9 — Stock / State-Machine DP

State = (day, holding?, transactions_left, cooldown?).

// Best Time to Buy and Sell Stock (unlimited) — LC 122
function maxProfit(prices) {
  let hold = -Infinity, cash = 0;
  for (const p of prices) {
    const newHold = Math.max(hold, cash - p);
    cash = Math.max(cash, hold + p);
    hold = newHold;
  }
  return cash;
}

Variant	Extra state
At most 1 transaction	dp[i][0/1], no k
Unlimited	same as above
At most k transactions	dp[i][k][0/1]
Cooldown	extra cooldown state
With fee	subtract fee on sell

---

14) Pattern 10 — Tree DP

DFS postorder; each node returns a tuple of states for its parent.

// House Robber III (LC 337)
function rob(root) {
  const dfs = (node) => {
    if (!node) return [0, 0];                 // [rob, notRob]
    const [lr, ln] = dfs(node.left);
    const [rr, rn] = dfs(node.right);
    return [node.val + ln + rn, Math.max(lr, ln) + Math.max(rr, rn)];
  };
  return Math.max(...dfs(root));
}
// Time O(n), Space O(h)

Examples: Diameter of Binary Tree, House Robber III, Binary Tree Max Path Sum, LIS in Tree, Tree Coloring.

---

15) Pattern 11 — DP on Graph / DAG

• DAG → topological order → relax edges (shortest/longest path).
• General graph + DP usually needs Bellman-Ford or BFS layering.

// Cheapest Flights Within K Stops (LC 787) — Bellman-Ford style
function findCheapestPrice(n, flights, src, dst, K) {
  let dist = new Array(n).fill(Infinity); dist[src] = 0;
  for (let i = 0; i <= K; i++) {
    const next = dist.slice();
    for (const [u, v, w] of flights)
      if (dist[u] + w < next[v]) next[v] = dist[u] + w;
    dist = next;
  }
  return dist[dst] === Infinity ? -1 : dist[dst];
}
// Time O(K * E)

---

16) Pattern 12 — Bitmask DP

Use when N ≤ ~20 and state needs subset of items.

State: dp[mask] or dp[mask][i] = best with subset mask, ending at i.

// Traveling Salesman (Held-Karp) sketch
const dp = Array.from({length: 1 << n}, () => new Array(n).fill(Infinity));
dp[1][0] = 0;
for (let mask = 1; mask < (1 << n); mask++)
  for (let u = 0; u < n; u++) {
    if (!(mask & (1 << u))) continue;
    for (let v = 0; v < n; v++) {
      if (mask & (1 << v)) continue;
      const next = mask | (1 << v);
      dp[next][v] = Math.min(dp[next][v], dp[mask][u] + cost[u][v]);
    }
  }
// Time O(2^n * n^2)

Examples: TSP, Assign Tasks to Workers, Partition to K Equal Subsets, Shortest Superstring, Min Cost to Connect Sticks.

---

17) Pattern 13 — Digit DP

Count numbers from 1 to N with some digit property.

State: dp[pos][tight][...properties].

function digitDP(N) {
  const s = String(N), n = s.length;
  const memo = new Map();
  function f(i, tight, ...props) {
    if (i === n) return /* base case */ 1;
    const key = `${i},${tight},${props.join(',')}`;
    if (memo.has(key)) return memo.get(key);
    const limit = tight ? +s[i] : 9;
    let res = 0;
    for (let d = 0; d <= limit; d++) {
      res += f(i + 1, tight && d === limit, /* update props */);
    }
    memo.set(key, res);
    return res;
  }
  return f(0, true);
}

Examples: Count numbers with no consecutive same digits, Numbers with K=1 digit, Sum of digit sums.

---

18) Pattern 14 — Game Theory DP

Two players, optimal play, minimax.

// Stone Game — pick from ends, max diff for current player
function stoneGameDP(piles) {
  const n = piles.length;
  const dp = Array.from({length: n}, () => new Array(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = piles[i];
  for (let len = 2; len <= n; len++)
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
    }
  return dp[0][n-1] > 0;
}

Examples: Stone Game, Predict the Winner, Nim Game, Can I Win, Soup Servings.

---

19) Pattern 15 — Counting DP

Problem	Recurrence
Unique Paths	dp[i][j] = dp[i-1][j] + dp[i][j-1]
Unique BST (Catalan)	dp[n] = Σ dp[i] * dp[n-1-i]
Number of Dice Rolls = Target	dp[i][s] = Σ dp[i-1][s-f] for f=1..k
Domino & Tromino Tilings	linear recurrence
Number of LIS	track count + length

---

20) Pattern 16 — Probability DP

dp[state] = probability of being in state.

// Knight Probability in Chessboard (LC 688)
function knightProbability(N, K, r, c) {
  const moves = [[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]];
  let dp = Array.from({length: N}, () => new Array(N).fill(0));
  dp[r][c] = 1;
  for (let k = 0; k < K; k++) {
    const nx = Array.from({length: N}, () => new Array(N).fill(0));
    for (let i = 0; i < N; i++)
      for (let j = 0; j < N; j++)
        if (dp[i][j])
          for (const [di, dj] of moves) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < N && nj >= 0 && nj < N) nx[ni][nj] += dp[i][j] / 8;
          }
    dp = nx;
  }
  return dp.flat().reduce((a, b) => a + b, 0);
}

---

21) Space-Optimization Tricks

Pattern	Trick
dp[i] depends only on dp[i-1], dp[i-2]	Two scalars
dp[i][j] depends only on previous row	Roll to 1D
0/1 Knapsack 1D	iterate w descending
Unbounded Knapsack 1D	iterate w ascending
LCS 1D	keep prev row + diagonal temp
Interval DP	usually can't reduce dimensions

---

22) Master Complexity Table

Pattern	Time	Space (after opt)
Linear 1D (Fib family)	O(n)	O(1)
Grid 2D paths	O(m·n)	O(n)
0/1 Knapsack	O(n·W)	O(W)
Unbounded Knapsack	O(n·W)	O(W)
LCS / Edit Distance	O(m·n)	O(min(m,n))
LIS	O(n log n)	O(n)
Palindrome DP	O(n²)	O(n²)
Interval DP (MCM, Burst)	O(n³)	O(n²)
Partition DP (Word Break)	O(n²)	O(n)
Tree DP	O(n)	O(h)
DAG DP / Bellman-Ford	O(V+E) / O(V·E)	O(V)
Bitmask DP	O(2ⁿ · n) or O(2ⁿ · n²)	O(2ⁿ · n)
Digit DP	O(D · states)	O(D · states)
Game DP (range)	O(n²) – O(n³)	O(n²)
Probability DP (grid+steps)	O(K · m · n)	O(m · n)

---

23) Common Mistakes Checklist

1. Wrong state definition → if you can't write a clean recurrence, redefine state.
2. Wrong iteration order in tabulation (depends on already-computed cells).
3. 0/1 vs Unbounded knapsack loop direction mixed up — descending vs ascending w.
4. Coin Change "ways" loops swapped → permutations vs combinations.
5. Forgetting base cases (especially dp[0] = 1 for "ways" problems).
6. Off-by-one in 1-indexed vs 0-indexed dp arrays.
7. Using memoization with mutable args (always pass primitives or stringify).
8. Tree DP returning wrong tuple shape — always document what each return slot means.
9. Bitmask iterating subsets wrong — for sub-subsets use for (sub = mask; sub; sub = (sub-1) & mask).
10. Game DP from wrong perspective — always model "current player's max diff".
11. Recursion stack overflow on deep DPs — convert to iterative.
12. Integer overflow in counting DPs (use BigInt or % MOD).
13. Floyd-style "all-pairs" reused for single source — wasteful, prefer Dijkstra/BF.

---

24) Recurrence Quick-Look

Goal	Template
Min cost to reach target	dp[i] = min over choices c of dp[i-c] + cost(c)
Count ways to reach target	dp[i] = Σ dp[i-c]
Yes/No reach target	dp[i] = OR dp[i-c]
0/1 pick item or not	dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt]+val)
Unbounded pick	dp[i][w] = max(dp[i-1][w], dp[i][w-wt]+val)
Match strings (LCS-like)	match: 1 + dp[i-1][j-1], else max(dp[i-1][j], dp[i][j-1])
Interval split	dp[i][j] = min over k of dp[i][k] + dp[k+1][j] + merge(i,k,j)
Minimax game	dp[i][j] = max over move of (gain - dp[opponent])
Tree DP	dfs(node) returns tuple combining child tuples

---

25) One-Line Super Formula

Min/max cost to target → dp[i] = min(dp[i-c] + cost) for all choices c.
Count ways → sum over choices; watch loop order for combinations vs permutations.
Pick subset (cap) → 0/1 vs unbounded knapsack (loop direction matters).
Two-string compare → 2D dp[i][j] (LCS template).
Range merge → Interval DP, iterate by length, O(n³).
Subset state, small N → Bitmask DP.
Tree → postorder DFS returning tuple.
Optimal play → minimax: dp = max(value - dp[opponent]).
Probability → dp[state] summing weighted transitions.

---

26) Code Index (this repo)

Topic	File
Linear 1D	Dynamic_Programming/minCostClimbingStairs.js, rob1.js
Counting (Stairs/BST/Tilings)	Dynamic_Programming/counting/climbStairs.js, numTrees.js, numTilings.js, numRollsToTarget.js, combinationSum4.js
Grid paths	Dynamic_Programming/grid-paths/minPathSum.js, minFallingPathSum.js, Triangle.js, maximalSquare.js
0/1 Knapsack	Dynamic_Programming/knapsack/canPartition.js, lastStoneWeightII.js, findTargetSumWays.JS, countSubsets.js, countPartionSubsetWithK.js, ones-and-zeroes.js
Unbounded Knapsack	Dynamic_Programming/knapsack/coinChange.js, rodLength.js
Subsequence / String DP	Dynamic_Programming/subsequence/longestCommonSubsequence.js, longestPalindromeSubseq.js, longestPalindromeSubString.js, countPalindromeSubstrings.js, findNumberOfLIS.js, minInsertions.js, shortestCommonSupersequence.js
Stock / state-machine	Dynamic_Programming/stock-problems/StockBuySell2.js, StockBuySell3.js
Game theory / probability	Dynamic_Programming/game-theory/getMoneyAmount.js, knightProbability.js, soupServings.js
Interval DP	Dynamic_Programming/mctFromLeafValues.js
Misc	Dynamic_Programming/mincostTickets.js, mostPoints.js, ninjaTraining.js, knightDialer.js, getMinOperations.js, deleteNearn.js
Existing pattern doc	Dynamic_Programming/DP_Patterns.md, Notes.md