Dynamic Programming

1 — What Is Dynamic Programming?

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems and storing the results of each subproblem to avoid redundant computation. It is applicable when a problem has optimal substructure (an optimal solution is built from optimal sub-solutions) and overlapping subproblems (the same subproblem is solved multiple times in naive recursion).

1.1 — The Four-Step DP Framework

1. STEP 1 — DEFINE THE STATE: What does dp[i] (or dp[i][j]) represent? Be precise. Write it in plain English first.
2. STEP 2 — WRITE THE RECURRENCE: How does dp[i] relate to smaller subproblems dp[i-1], dp[i-2], ...? This is the heart of the solution.
3. STEP 3 — IDENTIFY BASE CASES: What are the smallest subproblems with known answers? Fill these first to avoid out-of-bounds access.
4. STEP 4 — DETERMINE FILL ORDER: Which order guarantees that when computing dp[i], all required dp[j < i] are already filled? (Usually left-to-right for 1D, top-left to bottom-right for 2D.)

1.2 — DP vs Greedy vs Backtracking

2 — Visual Diagrams: DP in Action

Diagram 1 — Fibonacci: Naive vs Memoised

Fibonacci: Why Memoisation Eliminates Redundancy
  fib(5) — NAIVE RECURSION (no memoisation):
                    fib(5)
                  /       \
              fib(4)       fib(3)
             /     \       /    \
          fib(3) fib(2) fib(2) fib(1)
          /   \
       fib(2) fib(1)
fib(2) computed 3 times, fib(3) computed 2 times -> exponential O(2^n).
fib(5) — WITH MEMOISATION:
memo = {}
fib(5) -> fib(4) -> fib(3) -> fib(2) -> fib(1) = 1, fib(0) = 0
fib(2) = 1 -> stored in memo[2]
fib(3) = fib(2)+fib(1) = 2 -> stored in memo[3]
fib(4) = fib(3)+fib(2) = 3 -> stored in memo[4]  <- fib(2) read from memo
fib(3) already in memo -> return memo[3] = 2
fib(5) = fib(4)+fib(3) = 5
Each subproblem solved ONCE. Total: O(n) time, O(n) space.

Diagram 2 — Coin Change DP Table

Coin Change: Full DP Table Trace
  coins = [1, 5, 6, 9]   amount = 11
  dp[i] = minimum coins to make amount i.  dp[0] = 0, rest = INF initially.
i=0:  dp[0] = 0
i=1:  try coin 1: dp[1-1]+1 = dp[0]+1 = 1.  dp[1] = 1
i=2:  try coin 1: dp[1]+1 = 2.  dp[2] = 2
i=3:  try coin 1: dp[2]+1 = 3.  dp[3] = 3
i=4:  try coin 1: dp[3]+1 = 4.  dp[4] = 4
i=5:  try coin 1: dp[4]+1 = 5.
try coin 5: dp[0]+1 = 1.  dp[5] = 1   <- coin 5 wins
i=6:  try coin 1: dp[5]+1 = 2.
try coin 5: dp[1]+1 = 2.
try coin 6: dp[0]+1 = 1.  dp[6] = 1   <- coin 6 wins
i=7:  try coin 1: dp[6]+1 = 2.
try coin 5: dp[2]+1 = 3.
try coin 6: dp[1]+1 = 2.  dp[7] = 2
i=8:  coin 1: dp[7]+1=3. coin 5: dp[3]+1=4. coin 6: dp[2]+1=3. dp[8]=3
i=9:  coin 1: dp[8]+1=4. coin 5: dp[4]+1=5. coin 6: dp[3]+1=4.
coin 9: dp[0]+1=1.  dp[9] = 1   <- coin 9 wins
i=10: coin 1: dp[9]+1=2. coin 5: dp[5]+1=2. coin 6: dp[4]+1=5.
coin 9: dp[1]+1=2.  dp[10] = 2
i=11: coin 1: dp[10]+1=3. coin 5: dp[6]+1=2. coin 6: dp[5]+1=2.
coin 9: dp[2]+1=3.  dp[11] = 2
Answer: dp[11] = 2  (coins 5+6 or coins 2+9).  Correct!

Diagram 3 — LCS DP Table

LCS: DP Table Fill and Traceback
  s1 = 'ABCDE'   s2 = 'ACE'
  dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
   ''  A  C  E
''  0  0  0  0
A   0  1  1  1
B   0  1  1  1
C   0  1  2  2
D   0  1  2  2
E   0  1  2  3   <- answer: dp[5][3] = 3
Recurrence:
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1  (extend LCS)
else:                  dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Trace the LCS: start at dp[5][3]=3.
E==E (match): go diagonal to dp[4][2]=2. Track ‘E’.
D!=C:  max(dp[3][2], dp[4][1]) = max(2,1) -> came from dp[3][2].
C==C (match): go diagonal to dp[2][1]=1. Track ‘C’.
B!=A:  max(dp[1][1], dp[2][0]) = max(1,0) -> came from dp[1][1].
A==A (match): go diagonal to dp[0][0]=0. Track ‘A’.
LCS = ‘ACE’ (reversed tracking).  Length 3.  Correct!

Diagram 4 — 0/1 Knapsack DP Table

0/1 Knapsack: DP Table Fill
  items = [(w=2,v=6), (w=3,v=10), (w=4,v=12)]   capacity W = 5
  dp[i][w] = max value using first i items with capacity w.
    w: 0   1   2   3   4   5
i=0    : 0   0   0   0   0   0
i=1(2,6) : 0   0   6   6   6   6
i=2(3,10): 0   0   6  10  10  16  <- 16 = v1+v2 = 6+10
i=3(4,12): 0   0   6  10  12  16
Answer: dp[3][5] = 16.  Items selected: (w=2,v=6) + (w=3,v=10).
Recurrence:
if items[i-1].w > w: dp[i][w] = dp[i-1][w]                      // can’t include
else: dp[i][w] = max(dp[i-1][w],                                // exclude
dp[i-1][w - items[i-1].w] + items[i-1].v)  // include

3 — Real-World Use Cases

4 — Core Concepts: DP Patterns

4.1 — 1D DP: Climbing Stairs / Fibonacci

4.2 — 1D DP: Coin Change

4.3 — 1D DP: Longest Increasing Subsequence (LIS)

</div>
<h3>4.4 — 2D DP: Longest Common Subsequence</h3>
<div class="ch-code-wrap">
```cpp
// LeetCode 1143 — Longest Common Subsequence
// Time: O(m*n)  Space: O(m*n) -> O(n) with rolling array
int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;      // chars match: extend
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // skip one char
        }
    }
    return dp[m][n];
}

// Space-optimised: O(n) using two rolling rows
int lcs_space(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<int> prev(n+1,0), curr(n+1,0);
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++)
            curr[j] = s1[i-1]==s2[j-1] ? prev[j-1]+1 : max(prev[j],curr[j-1]);
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[n];
}

4.5 — 0/1 Knapsack

</div>
<h3>4.6 — State Machine DP: Stock Problems</h3>
<div class="ch-code-wrap">
```cpp
// Best Time to Buy and Sell Stock with Cooldown (LC 309)
// States: held (holding stock), sold (just sold), rest (cooldown done)
// Time: O(n)  Space: O(1)
int maxProfit(vector<int>& prices) {
    int held = INT_MIN, sold = 0, rest = 0;
    for (int p : prices) {
        int prevHeld = held, prevSold = sold, prevRest = rest;
        held = max(prevHeld, prevRest - p);  // hold: keep or buy from rest
        sold = prevHeld + p;                  // sell: was holding, now sell
        rest = max(prevRest, prevSold);       // rest: keep resting or cooldown
    }
    return max(sold, rest); // can't end holding stock
}
// State transition diagram:
// rest -> held (buy)    held -> sold (sell)    sold -> rest (cooldown)
// rest -> rest (wait)   held -> held (hold)

4.7 — Interval DP: Burst Balloons

5 — Pattern Recognition Guide

6 — Complete C++ Implementations

6.1 — Edit Distance (Levenshtein)

6.2 — Unique Paths on Grid

</div>
<h3>6.3 — Word Break</h3>
<div class="ch-code-wrap">
```cpp
// LeetCode 139 — Word Break
// Can string s be segmented into words from wordDict?
// Time: O(n^2 * L)  L=avg word length  Space: O(n)
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> ws(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n+1, false);
    dp[0] = true; // empty string always segmentable
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // If prefix s[0..j-1] is breakable AND s[j..i-1] is a word
            if (dp[j] && ws.count(s.substr(j, i-j))) {
                dp[i] = true;
                break; // found one valid split, no need to check more
            }
        }
    }
    return dp[n];
}

7 — Complexity Reference

8 — Solved Problem 1: Coin Change

Given an integer array coins and an integer amount, return the fewest number of coins needed to make up amount. If it is impossible, return -1. You may use each coin denomination an unlimited number of times.

    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (c <= i)  // coin c can contribute to amount i
                dp[i] = min(dp[i], dp[i-c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

</div>
<p><strong>Complexity:</strong> Time O(amount * n), Space O(amount)</p>
</section>
<!-- SECTION 9 -->
<section id="section-9" class="chapter-section">
<h2> 9 — Solved Problem 2: Longest Common Subsequence</h2>
<p>Given two strings <code>text1</code> and <code>text2</code>, return the length of their longest common subsequence (LCS). A subsequence is a sequence derived by deleting some characters without changing the relative order of the remaining characters.</p>
<div class="insight-box">
<h4>OBSERVATIONS</h4>
<ul>
<li>A subsequence is NOT a substring — characters don't need to be contiguous.</li>
<li>State definition: <code>dp[i][j]</code> = length of LCS of <code>text1[0..i-1]</code> and <code>text2[0..j-1]</code>. 1-indexed to simplify base cases.</li>
<li>Recurrence: If <code>text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1</code> (extend LCS by matching char). Else: <code>dp[i][j] = max(dp[i-1][j], dp[i][j-1])</code> (skip one char from either string).</li>
<li>Base cases: <code>dp[0][j] = 0</code> (empty text1) and <code>dp[i][0] = 0</code> (empty text2). Automatically initialised by vector constructor.</li>
<li>Fill order: row by row, left to right. <code>dp[i][j]</code> only depends on <code>dp[i-1][j-1]</code>, <code>dp[i-1][j]</code>, <code>dp[i][j-1]</code> — all already computed.</li>
</ul>
</div>
<div class="ch-code-wrap">
```cpp
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        // Space-optimised: use two rows only
        vector<int> prev(n+1, 0), curr(n+1, 0);

        for (int i = 1; i <= m; i++) {
            fill(curr.begin(), curr.end(), 0);
            for (int j = 1; j <= n; j++) {
                if (text1[i-1] == text2[j-1])
                    curr[j] = prev[j-1] + 1;         // chars match
                else
                    curr[j] = max(prev[j], curr[j-1]); // skip one
            }
            swap(prev, curr);
        }
        return prev[n];
    }
};

Complexity: Time O(m*n), Space O(n)

10 — Common Mistakes & Edge Cases

10.1 — State Definition Mistakes

• Imprecise state definition. dp[i] must have an exact meaning. 'dp[i] = something about index i' is not enough — write 'dp[i] = minimum cost to reach index i from index 0 using exactly i steps'.
• Off-by-one in string/array DP. When using 1-indexed dp (dp[1..n] for string of length n), always access text[i-1] for the i-th character. Mixing 0-indexed and 1-indexed causes subtle bugs.
• Wrong base case. For coin change, initialising dp[0] = 0 is critical. For LCS, the entire dp[0][j] and dp[i][0] row/column must be 0. For path counting, dp[0][0] = 1.
• Missing the 'impossible' sentinel. For coin change, initialise to amount+1 (not INT_MAX — adding 1 to INT_MAX overflows). For paths, -1 or 0 are natural sentinels.

10.2 — Knapsack Direction Mistakes

• 0/1 knapsack — iterating capacity forward in the 1D optimisation. This allows the same item to be used multiple times (becomes unbounded knapsack). Always iterate capacity in REVERSE for 0/1 knapsack.
• Coin Change II (combinations) — iterating loops in wrong order. Iterating coins in inner loop and amounts in outer counts permutations (e.g. [1,2] and [2,1] counted separately). Swap the loops: outer = coins, inner = amounts.
• Confusing 'at most W' capacity with 'exactly W'. For knapsack, dp[W] gives the answer for capacity AT MOST W. For 'exactly W' problems, initialise with -infinity except dp[0]=0.

10.3 — Edge Cases

• Empty string LCS: if either string is empty, LCS = 0. Base cases dp[0][j]=dp[i][0]=0 handle this.
• No valid coin combination: return -1, not 0. Check if dp[amount] > amount after filling.
• amount = 0 for coin change: always return 0 (zero coins needed). dp[0] = 0 handles this.
• Identical strings for LCS: LCS = the string itself. dp[n][n] = n.
• All-negative array for max subarray: Kadane returns the single maximum element (not 0). Initialise both currSum and maxSum to nums[0].

11 — Common Interview Questions