Phase 4: Dynamic Programming

M6 – M7.5 | Weeks 24–30 | Jan 12 – Feb 22, 2027

Most people quit DP not because it’s impossible, but because they try to memorize 200 solutions instead of recognizing the 7 underlying patterns. Every DP problem you will ever encounter is a variant of one of those 7 patterns. Learn the patterns. The solutions follow automatically.

The correct mental model for DP is this: “Can I express the answer to a bigger problem in terms of answers to smaller subproblems — and do those subproblems repeat?” If yes, you have a DP problem. The skill is recognizing which of the 7 structural forms it takes, then designing the state and transition correctly. State design is the hard part. Everything else is mechanical.

This phase has the highest attrition of the entire roadmap — not because DP is harder than graphs or trees, but because the feedback loop is brutal. You either see it or you don’t, and beginners often spend two weeks grinding without a framework and make no progress. This guide is that framework.

The 7 DP Patterns

Pattern

Canonical Problem

Key State Design Insight

1D Linear

House Robber, Coin Change

dp[i] = best answer considering first i items

2D Grid

Unique Paths, Edit Distance

dp[i][j] = best answer for position (i,j) or prefixes of length i,j

Knapsack

0/1 Knapsack, Partition Equal Subset Sum

dp[i][w] = best answer using first i items with capacity w

Interval

Burst Balloons, Matrix Chain Multiplication

dp[i][j] = best answer for the subarray/range [i..j]

Subsequence

LIS, LCS, Edit Distance

State tracks position in one or two sequences

Tree DP

House Robber III, Tree Diameter

DP on tree nodes, computed bottom-up via DFS

Bitmask DP

Traveling Salesman, Task Assignment

dp[mask][i] = best answer after visiting subset encoded by mask, last at i

Why This Phase Has the Highest Attrition

Three reasons people fail here, in order of lethality:

  1. Wrong entry point. They start with LeetCode Hard problems before understanding overlapping subproblems. Start with foundations, not problems.

  2. Memorizing instead of deriving. You can memorize the coin change solution in 10 minutes and still be unable to solve a novel problem 2 months later. Derive every recurrence from scratch.

  3. Skipping state design. The state is not the problem — it’s the decision. Most DP bugs are incorrect state definitions, not coding errors.

Phase Files

File

Topic

Difficulty

01_dp_foundations.md

Overlapping subproblems, memoization, tabulation, state design

Foundation

02_1d_and_linear_dp.md

Fibonacci, House Robber, Coin Change, Jump Game

Easy–Medium

03_2d_grid_dp.md

Grid paths, Edit Distance, LCS

Medium

04_knapsack_patterns.md

0/1, Unbounded, Bounded, Subset Sum

Medium–Hard

05_interval_and_subsequence_dp.md

Burst Balloons, LIS, Palindrome DP

Hard

06_tree_dp_and_bitmask.md

Tree DP, TSP via bitmask

Hard

07_dp_pattern_recognition.md

The meta-skill: pattern taxonomy + recognition

Meta

08_exit_criteria_and_projects.md

What “done” looks like + 3 projects

Deliverables