Rung 6: Dynamic Programming Pattern Handbook¶

Month: M7–M8 (January 2027 – February 2027) Platform: GitHub (public repo + formatted README) + submitted to r/learnprogramming or r/competitiveprogramming Hard Gate: YES — must be complete by end of M8.5 (mid-March 2027). This is non-negotiable.

Why This Is a Hard Gate¶

Dynamic programming is the single highest-leverage topic in DSA. It separates people who can solve problems from people who can categorize problems — and categorization is what competitive programming and hard LeetCode problems demand. If you haven’t synthesized DP into a personal framework by Month 8.5, the Codeforces Rung 7 target becomes nearly unachievable. These two hard gates depend on each other.

A handbook also forces a specific kind of mastery: you cannot write “when to recognize this pattern” unless you actually recognize it. You cannot write “state design formula” unless you’ve derived the state from scratch. The act of writing the handbook is the learning verification.

What It Is¶

A public document titled dp-pattern-handbook — a GitHub repository containing your personal dynamic programming reference, written entirely in your own words, covering all 7 core DP patterns. Not copied from any existing handbook (NeetCode, Striver, or any other). Every worked example must be one you solved yourself. Every explanation must be reconstructed from your own understanding.

This handbook is written for you-in-6-months, who has forgotten the details. It assumes you know what recursion and arrays are, and nothing else.

Repository Structure¶

dp-pattern-handbook/
├── README.md                    # Overview, how to use this handbook, pattern index
├── 01_1d_linear_dp.md
├── 02_2d_grid_dp.md
├── 03_knapsack_dp.md
├── 04_interval_dp.md
├── 05_subsequence_dp.md
├── 06_state_machine_dp.md
├── 07_tree_dp.md
├── problems_index.md            # All problems referenced, organized by pattern
└── derivation_template.md       # Blank template for solving new DP problems

The 7 Patterns — What Each Chapter Must Contain¶

Every chapter follows the same structure. No exceptions. The structure is the discipline.

Chapter Structure (repeat for all 7 patterns)¶

## [Pattern Name]

### What It Is
2-4 sentences. What is the defining characteristic of this pattern.
Not "problems that can be solved with DP" — the specific structural property
that makes this pattern distinct from others.

### When to Recognize It
A list of trigger phrases and constraint signatures:
- "minimum/maximum cost to reach..."
- "number of ways to..."
- Array length ≤ 1000 (suggests O(n²) is acceptable)
- etc.

### State Design Formula
How do you define dp[i] or dp[i][j]?
The formula is: "dp[i] represents _____ for/at/up to index i"
Write this out explicitly. It is the hardest part and the most important.

### Transition Formula
The recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)
Write it in math notation AND in plain English.
Explain WHY this transition is correct — what decision is being made at step i?

### Base Cases
What are dp[0], dp[1], etc.?
Why do these values make sense?
What breaks if you get them wrong?

### Iteration Order
Left to right? Right to left? Diagonal?
WHY does the order matter for this pattern?

### Space Optimization
Can the full table be compressed to O(1) or O(n)?
If yes, show the transformation explicitly.
If no, explain why the full table is necessary.

### Canonical Problem
One problem that is the clearest, most direct example of this pattern.
Include: problem statement, your state definition, transition, code, complexity.
This must be a problem you solved yourself — not copied.

### Additional Problems (2-3)
Same format: problem name, why it fits this pattern, your implementation.
At least one must be a hard LeetCode problem.

### What Most People Get Wrong
The specific mistake that trips people up in this pattern.
Not generic advice — the exact pitfall, the exact symptom, the exact fix.

The 7 Patterns¶

Pattern 1: 1D Linear DP¶

Defining characteristic: State depends only on previous elements in a single 1D array. No second dimension, no interval, no tree structure.

Canonical problems: Climbing Stairs, House Robber, Fibonacci (trivial but instructive), Jump Game II (harder), Decode Ways.

State template: dp[i] = some optimal value/count for the first i elements.

The hard problem to include: Decode Ways (LeetCode 91) — the edge cases are what make it hard, not the pattern recognition.

Pattern 2: 2D Grid DP¶

Defining characteristic: You traverse a 2D grid and the optimal solution at each cell depends on adjacent cells (typically top and left, or top/bottom/left/right).

Canonical problems: Unique Paths, Minimum Path Sum, Dungeon Game (harder, reversed iteration), Maximal Square.

State template: dp[i][j] = some optimal value for the subgrid from (0,0) to (i,j).

The hard problem to include: Maximal Square (LeetCode 221) — the transition is non-obvious and worth deriving slowly.

Critical insight to explain: Why Dungeon Game requires right-to-left, bottom-to-top iteration. This destroys most people who try to solve it left-to-right. Explain the invariant violation that occurs with naive direction.

Pattern 3: Knapsack DP¶

Defining characteristic: You have a set of items and a capacity constraint. You must decide to include/exclude each item to optimize some value. Classic bounded vs unbounded distinction.

Three subtypes (all must be covered):

0/1 Knapsack — each item used at most once
Unbounded Knapsack — each item used any number of times
Fractional Knapsack — NOT DP (greedy), include to explain why

Canonical problems: Partition Equal Subset Sum (0/1), Coin Change (unbounded), Coin Change II (count ways, subtle).

State template for 0/1: dp[i][w] = max value using first i items with capacity w. Then show the 1D space-optimized version and explain the reverse iteration requirement.

The hard problem to include: Target Sum (LeetCode 494) — disguised as a knapsack problem, most people don’t see the transformation. Show the transformation from ±assignment to subset sum.

Critical insight: Why 0/1 knapsack iterates the weight dimension in reverse when space-optimized, and unbounded iterates forward. This is the most commonly confused detail.

Pattern 4: Interval DP¶

Defining characteristic: The problem involves a range [i, j] and the solution depends on breaking the range at some pivot k, then combining results from [i, k] and [k+1, j].

Canonical problems: Matrix Chain Multiplication, Burst Balloons (hard, excellent), Palindrome Partitioning II, Minimum Cost to Cut a Stick.

State template: dp[i][j] = optimal cost/value for the subproblem on interval [i, j].

Iteration order: ALWAYS by interval length. Why? Because dp[i][j] depends on smaller intervals. Explicitly show the nested loop:

for length in 2..n:
  for i in 0..n-length:
    j = i + length - 1
    for k in i..j-1:  # all split points
      dp[i][j] = optimize(dp[i][k], dp[k+1][j])

The hard problem to include: Burst Balloons (LeetCode 312) — the key insight is framing “last balloon burst” rather than “first balloon burst.” Explain why the inversion is necessary and how to derive it.

Pattern 5: Subsequence DP¶

Defining characteristic: Problems about subsequences of one or two strings — longest common subsequence, edit distance, longest palindromic subsequence.

Canonical problems: Longest Common Subsequence, Edit Distance (hard), Longest Palindromic Subsequence, Wildcard Matching (very hard).

State template for two-string problems: dp[i][j] = optimal value for the first i chars of string A and first j chars of string B.

The transition tree: Show all cases for LCS vs Edit Distance side by side. The structural similarity makes the distinction memorable.

Critical insight: How LCS transforms into edit distance by adding insert/delete/replace operations. Derive Edit Distance from LCS formally — most people treat them as unrelated.

The hard problem to include: Edit Distance (LeetCode 72). Walk through the full derivation. This is one of the most important DP problems in existence.

Pattern 6: State Machine DP¶

Defining characteristic: You are at one of several discrete states (e.g., “holding stock,” “not holding stock,” “in cooldown”) and transition between states based on decisions. The number of states is small and explicitly enumerable.

Canonical problems: Best Time to Buy and Sell Stock II (unlimited transactions), Best Time to Buy and Sell Stock III (at most 2 transactions), Best Time to Buy and Sell Stock with Cooldown, Best Time to Buy and Sell Stock with Transaction Fee.

State template: Define all states explicitly as an enum or named variables. For stock problems: held, not_held, cooldown. Transition formula is written as state machine transitions.

Critical insight: Most people solve each stock variant as a separate problem. The unified state machine view shows they are all the same problem with different allowed transitions. Show the state machine diagram (ASCII is fine) and derive all variants from it.

The hard problem to include: Best Time to Buy and Sell Stock III (LeetCode 123) — at most 2 transactions forces a 3D state that most people manage incorrectly.

Pattern 7: Tree DP¶

Defining characteristic: The problem is on a tree (not a grid, not a sequence). State is defined per subtree. Solution at each node depends on solutions from its children.

Canonical problems: Diameter of Binary Tree, Maximum Path Sum in Binary Tree (hard), House Robber III (on a tree), Binary Tree Cameras.

State template: A recursive function that returns one or more values per node representing the optimal solution for the subtree rooted at that node.

Critical insight: Why tree DP problems often require returning multiple values from the recursive call. For Maximum Path Sum: the node must return both “max path through this node” (for the global answer) and “max path ending at this node” (for parent’s computation). Conflating these causes wrong answers.

The hard problem to include: Binary Tree Cameras (LeetCode 968) — requires defining 3 states per node. Walk through the state definition derivation.

The Derivation Template¶

Create derivation_template.md — a blank template you use for every new DP problem. This template is itself a portfolio artifact: it demonstrates that you have a systematic problem-solving process, not just intuition.

## Problem: [Name + Link]

### Step 1: Identify the pattern
Which of the 7 patterns does this resemble? Why?

### Step 2: Define the state
dp[...] = "_____ for/at/up to ..."
What does this value represent in plain English?

### Step 3: Write the transition
If I know dp[smaller subproblems], how do I compute dp[current]?
Write the recurrence in math notation.

### Step 4: Identify base cases
What are the smallest subproblems I can answer directly?

### Step 5: Determine iteration order
Which dimension do I iterate first? Which direction?

### Step 6: Implement top-down (memoization)
Write the recursive + memo version first. It's easier to verify correctness.

### Step 7: Convert to bottom-up (tabulation)
Now convert to iterative. Verify same output.

### Step 8: Optimize space (if possible)
Can the table be compressed? What invariant allows this?

### Complexity
Time: O(?)  Why?
Space: O(?)  Why?

Acceptance Criteria¶

All 7 patterns have complete chapters following the exact structure above
Every canonical problem and hard problem is YOUR implementation — no copied code
The derivation template exists and is populated for at least 10 problems
The problems_index.md lists every problem referenced across all chapters with pattern classification and difficulty
At least 3 people in r/learnprogramming, r/competitiveprogramming, or a Discord community comment that the handbook is useful (screenshot or link these)
The root README has a clear table of contents with one-sentence descriptions of each pattern
No chapter contains the phrase “as we all know” — every claim is derived or explained

Signal It Sends¶

Most people consume DP resources. This handbook is produced from understanding. The act of writing “when to recognize it” and “what most people get wrong” requires having been the person who didn’t recognize it and made the mistakes. It demonstrates synthesis, not recall.

A handbook that community members call useful is proof that your understanding is communicable — which is a higher bar than understanding it privately. This is why the community submission criterion exists: it’s not vanity, it’s a calibration check.

Hard Gate: Why M8.5 is the Deadline¶

If this handbook isn’t done by mid-March 2027, Codeforces preparation (Rung 7) doesn’t have the conceptual backbone it needs. Div. 2 C and D problems are frequently DP-heavy. You need not just pattern recognition but the derivation speed that comes from having written these transitions out 50+ times.

The deadline is M8.5, not M8, because writing takes longer than expected. If you start this at the beginning of M7 (as planned), you should be done by M8.0 comfortably. The 0.5 month buffer is there for real life, not procrastination.

Platform Notes¶

GitHub: Primary home. The README is the handbook entry point. Use proper Markdown formatting — headers, code blocks, tables where needed.
PDF: Export a clean PDF version from Markdown (use Pandoc or a Markdown-to-PDF tool). This is optional but makes it shareable as a single file.
Community submission: Post to r/learnprogramming with title “I spent 2 months writing a DP handbook from scratch — [link]”. Be honest about what it is. Don’t oversell. The community will tell you if it’s good.

Month M7–M8 Timeline¶

Week	Goal
M7 Week 1	Patterns 1–2 (1D Linear, 2D Grid) complete
M7 Week 2	Pattern 3 (Knapsack, all 3 subtypes) complete
M8 Week 1	Patterns 4–5 (Interval, Subsequence) complete
M8 Week 2	Patterns 6–7 (State Machine, Tree DP) + derivation template + problems index
M8 Week 3	Editing pass, community submission, address feedback

Navigation: ← Rung 5: Graph Showcase | Portfolio README | Rung 7: Codeforces →