Dynamic programming is recursion with a memo — you break a problem into overlapping subproblems, solve each once, and reuse solutions. Like asking for directions in an unfamiliar city: instead of navigating from scratch every time you cross the same intersection, you remember the best path from that point.

Given array $A[1..n]$, find longest subsequence (not necessarily contiguous) where each element > previous.

Result: Max DP = 3 (subsequence: [1, 2, 5]) O(n²) implementation:

O(n log n) optimization: Maintain array of smallest possible tail for each length.

Minimum operations (insert, delete, replace) to transform string $S$ into $T$.

i & \text{if } j = 0 \\ j & \text{if } i = 0 \\ DP[i-1][j-1] & \text{if } S[i] = T[j] \\ 1 + \min\{DP[i-1][j], DP[i][j-1], DP[i-1][j-1]\} & \text{otherwise} \end{cases}$$ ### 3.3 Tracing: "CAT" → "DOG" | | ε | D | O | G | |---|---|---|---|---| | ε | 0 | 1 | 2 | 3 | | C | 1 | 1 | 2 | 3 | | A | 2 | 2 | 2 | 3 | | T | 3 | 3 | 3 | 3 | Result: 3 operations (replace C→D, A→O, T→G). --- ## 4. Subset Sum ### 4.1 Problem Given set $A$ and target $T$, can any subset sum to $T$? ### 4.2 Recurrence DP[i][t] = DP[i-1][t] \lor DP[i-1][t-A[i]] ### 4.3 Tracing: A = [2, 3, 7, 8], T = 11 | | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | {} | T | F | F | F | F | F | F | F | F | F | F | F | | {2} | T | F | T | F | F | F | F | F | F | F | F | F | | {2,3} | T | F | T | T | F | T | F | F | F | F | F | F | | {2,3,7} | T | F | T | T | F | T | F | T | F | T | T | F | | {2,3,7,8} | T | F | T | T | F | T | F | T | T | T | T | T | Result: T (subset {3, 8} sums to 11) --- ## 5. Optimal BST ### 5.1 Problem Given keys $k_1 < k_2 < ... < k_n$ with probabilities $p_i$, find BST minimizing expected search cost. ### 5.2 Recurrence DP[i][j] = \min_{r=i..j} {DP[i][r-1] + DP[r+1][j] + \sum_{k=i}^j p_k} --- ## 6. Common Pitfalls ### Pitfall 1: Missing Base Cases The mistake: Forgetting to initialize DP[0] or DP[i][0] correctly. Why students make it: Recursive thinking focuses on the recurrence, skipping edge cases. Correct approach: Always define DP[0] or empty prefix cases first. Test with small inputs. ### Pitfall 2: Wrong Order of Computation The mistake: Computing DP[i] before DP[i-1] when DP[i] depends on DP[i-1]. Correct approach: For sequence DP, iterate forward. For interval DP (Optimal BST), iterate by length. ### Pitfall 3: Incorrect Space Optimization The mistake: Using a 1D array when 2D is needed, corrupting values needed for subsequent computations. Correct approach: For knapsack 0/1, iterate capacity backwards to avoid reusing items. For unbounded knapsack, iterate forwards. --- ## 7. Key Concepts Reference | Concept | Pattern | Example | |---------|---------|---------| | Sequence DP | DP[i] depends on DP[j] for j < i | LIS, LCS | | String DP | DP[i][j] from prefixes | Edit distance | | Partition DP | DP[i][t] from subsets | Subset sum | | Interval DP | DP[i][j] from sub-array | Optimal BST | | Time complexity | O(n²) typical, O(n log n) for LIS | Depends on recurrence | --- ## 8. 📝 Practice Questions > Q1: Solve LIS for A = [10, 22, 9, 33, 21, 50, 41, 60]. > > Answer: > DP: [1, 2, 1, 3, 2, 4, 4, 5] > LIS length = 5 (subsequence: 10, 22, 33, 50, 60 or 10, 22, 33, 41, 60) > Q2: Edit distance from "SATURDAY" to "SUNDAY". > > Answer: DP table gives 3 operations: Delete A, Delete T, Replace R→N (or equivalently delete T, A, replace R→N). Distance = 3. > Q3: Can DP[i] for LIS be computed independently of order? > > Answer: No — DP[i] depends on all DP[j] for j < i, requiring forward iteration. Computing LIS backwards gives decreasing subsequence instead. > Q4: For subset sum A = [1, 4, 5, 6], T = 9, find a subset. > > Answer: {4, 5} or {1, 4, ...} — check DP table: 9 is reachable via {4, 5}. DP tracing confirms. > Q5: Space-optimize the edit distance DP from O(mn) to O(min(m,n)). > > Answer: Use two rows (current and previous) since DP[i][j] depends only on DP[i-1][j], DP[i][j-1], DP[i-1][j-1]. Only keep previous row, compute current row left-to-right. O(min(m,n)) space. > Q6: When does DP use bottom-up vs. top-down? > > Answer: Bottom-up: all subproblems needed, iterative, avoids recursion overhead. Top-down: only needed subproblems computed, easier to code, but recursion overhead. Use top-down when the state space is sparse (many states unreachable). --- ## 9. 🔗 Cross-References - Week 1 - Greedy: Comparison of approaches - Week 4 - Network Flow: DP for flow - BSCS4020 (DSA): Basic recurrence analysis Join Discord PreviousMatroid TheoryNextNetwork Flow