DP Foundations 21-Day

DP gateway. Practice the three-line ritual out loud: state, transition, base. Every harder problem starts with this template.

Fibonacci with a story. The recurrence f(n) = f(n-1) + f(n-2) is the same — say it before you reach for code.

First problem where the transition takes a min(). Drill the 'cost to STAND on i vs cost to LEAVE i' framing — interviewers test that distinction.

Three-term recurrence. Use it to warm up rolling-array space optimization: 3 vars, no array needed.

Decision DP: rob this house or skip it. The 'two choices per state' pattern unlocks 30+ problems.

Same DP, run twice on different windows to handle the circular constraint. Name the trick: 'split the problem to remove the wraparound'.

Carry TWO states (max and min) because negative times negative flips. The first problem where 'one state is not enough' bites.

Kadane's algorithm in DP framing. dp[i] = max(nums[i], dp[i-1] + nums[i]). Say the reset condition out loud.

Greedy beats DP here — track farthest reach. But you must know the DP solution exists to defend the greedy in the interview.

BFS-flavored greedy: each 'level' is one jump's reach. The shape generalizes to minimum-steps-to-reach problems.

Unbounded knapsack in disguise. Drill the inner loop direction — coins outer, amount inner — and explain why.

1D DP over string prefixes. The state is 'can I segment s[:i]?' — name it before reaching for the substring check.

Counting DP with edge cases. The '0' character is the entire interview signal — handle it explicitly in your transition.

O(n^2) DP first, then patience-sort O(n log n). Know both. The trade is a classic follow-up.

0/1 knapsack reframe: target = total/2. The transformation step is the interview signal — articulate it before coding.

Grid DP with obstacles. The base-row initialization is where most candidates fumble — write it before the main loop.

Classic grid DP. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Template for every 'walk the grid' DP you'll see.

2D DP where the state is 'largest square ending HERE'. The min(three neighbors) + 1 transition is the whole problem — burn it in.

2D string DP. dp[i][j] = LCS of prefixes. Every string-DP problem (edit-distance, regex, wildcard) is a variant of this.

Three operations = three transitions: insert, delete, replace. Master the recursion tree before optimizing — interviewers ask 'why three?'

Capstone. 2D DP on intervals. You should now narrate state, transition, base, and answer-cell in under a minute.