Week 12 — Foundational DP + Graphs Bridge

Pivot week. Two threads in one push:

1. Foundational DP arc (p56–p61): the six canonical recurrences every senior must derive cold — House Robber, Coin Change, LIS (patience-sort O(n log n)), LCS, Edit Distance, Partition Equal Subset Sum. After this week, the vocabulary of DP is yours.
2. Graphs bridge (p62–p65): the four “must-know-before-Month-3-Graphs-deep” algorithms — topological sort with order output (Course Schedule II), Dijkstra, Bellman-Ford / SSSP with edge constraint (Cheapest Flights K Stops), Union-Find (Number of Connected Components).

This is the biggest week in the track. Ten problems. Done deliberately — the reader who completes Week 12 has crossed from “pattern-aware” to “algorithm-fluent.”

Why these ten problems together?

DP and Graphs are taught as separate worlds in textbooks. They are not. Graphs are DP on a DAG. Topological sort is the evaluation order for a graph DP. Dijkstra is a DP over “shortest path so far,” relaxed via a priority queue. Bellman-Ford is the literal recurrence dist[v] = min(dist[u] + w(u,v)) evaluated V-1 times.

By interleaving the two threads in one week, you’ll see — by week’s end — that Cheapest Flights K Stops is just Coin Change on a graph (knapsack-flavored relaxation under a step bound), and LIS with patience-sort is a hidden binary-search application that lifts the curtain on why O(n log n) DPs exist at all.

Mental models you’ll internalize

1. The DP recurrence ritual: state → transitions → base case → evaluation order → answer extraction. Apply it to every problem. Cold. In 60 seconds.
2. Knapsack family (unbounded vs 0/1, weight as DP dimension): Coin Change is unbounded; Partition Equal Subset Sum is 0/1; both reduce to “fill a sack.”
3. String-DP grid: LCS, Edit Distance — dp[i][j] over two string prefixes; the diagonal/up/left transitions are the three universal moves.
4. Patience-sort LIS: the elegant O(n log n) algorithm that turns LIS into “binary search on tails.” Reveals that some DPs collapse into much faster data-structure-driven algorithms.
5. Topological sort as DAG-DP evaluation order: Kahn’s BFS or DFS post-order. Both produce the order in which dp[node] can be safely computed.
6. Dijkstra ≡ DP relaxation + greedy ordering: when all edge weights ≥ 0, the priority queue is “evaluate states in order of best-so-far distance.” Proof rests on the cut property.
7. Bellman-Ford ≡ literal recurrence with bounded relaxation depth: the natural fit when you need “shortest path with at most K edges” — the K-stops constraint is the giveaway.
8. Union-Find: amortized α(N) “merge connectivity” oracle. Connected components is the simplest application; Kruskal MST and Tarjan offline LCA are the deeper ones.

Problem table

Daily schedule

• Mon: p56 House Robber → p57 Coin Change. Internalize “include vs skip” and “unbounded knapsack” templates.
• Tue: p58 LIS (BOTH O(n²) and patience-sort O(n log n) — they’re the same problem; the patience-sort lens is non-obvious). Then p59 LCS as your first 2D string DP to anchor the grid pattern.
• Wed: p60 Edit Distance — the capstone of 2D string DP; three transitions = insert, delete, substitute. Then p61 Partition Equal Subset Sum — translates “subset sum = half-total” into a 0/1 knapsack.
• Thu: p62 Course Schedule II — topological order extraction with BOTH Kahn and DFS post-order. Then p63 Network Delay Time — your first Dijkstra; binary-heap relaxation; correctness from the cut property.
• Fri: p64 Cheapest Flights K Stops — Bellman-Ford or BFS-with-state; key insight: the K-edges-bound makes this NOT Dijkstra. Then p65 Number of Connected Components — Union-Find with rank + path compression.

Readiness gate

By Sunday night, you can answer cold (in under 60 seconds each):

1. State the DP recurrence for Coin Change (unbounded) vs Partition Equal Subset Sum (0/1) without looking.
2. Write dp[i][j] for LCS and Edit Distance — state, transitions, base case, answer location.
3. Implement LIS in O(n log n) with bisect_left over the tails array; explain why patience-sort gives correct LIS length.
4. Distinguish when to use Dijkstra vs Bellman-Ford vs BFS-with-state. (Hint: edge weights, edge-count bound, negative weights.)
5. Sketch Kahn’s algorithm AND the DFS-post-order variant of topological sort; explain why both yield valid orderings.
6. Implement Union-Find with rank + path compression; prove (informally) why find is α(N) amortized.

If you can do all six cold, Month 3 Graphs Deep is open.