4.23.0 — 1-D Dynamic Programming: The Pattern

Recognition cue. The answer is a count, a best value, or a yes/no, and the state can be described by one number — usually a position in an array or string, or a remaining budget.

The tell that it is DP and not greedy: a choice made now restricts the choices available later. Greedy cannot see that; DP handles it by remembering the consequence.

If you are unsure, 4.22 section 2 has the full decision. The short version: spend thirty seconds hunting a counterexample to the greedy rule. If you find one, it is DP. If you cannot find one and cannot prove the rule either, write the DP — it is never wrong, only slower.

The question that produces the recurrence

For a 1-D DP, one question does almost all the work:

How did I get here?

List the ways to arrive at state i. They must be disjoint and must cover everything. Then combine them:

the problem asks	combine with
how many ways	+
fewest / cheapest	min
best / largest	max
is it possible	or

Climbing Stairs and Min Cost Climbing Stairs have the same two arrival routes and differ only in that operator.

The five questions, in order

1. What is the state? Say dp[i] in one English sentence. If you cannot, stop — nothing after this will work.
2. What are the choices at each state? Usually two or three.
3. What is the recurrence? Combine the choices with the right operator.
4. What are the base cases? Check them by hand on the smallest input. Most wrong DP solutions have a correct recurrence and a wrong base.
5. What order fills the table? Everything a cell reads must already be filled.

The state definition traps

"ending at i" versus "considering the first i". These are different states and they lead to different code.

• Longest Increasing Subsequence needs ending at i, because you must know the last element to extend it. The answer is then max(dp), not dp[n-1].
• House Robber uses considering the first i, so the answer is dp[n] directly.

Getting this backwards produces code that is nearly right and fails on half the tests. Say which one you are using out loud before writing anything.

The loop direction, which is not a detail

When a 1-D array is updated in place, the direction decides whether an item can be reused:

# each item used ONCE  → count DOWN
for item in items:
    for t in range(target, item - 1, -1):
        dp[t] = dp[t] or dp[t - item]

# items REUSABLE       → count UP
for item in items:
    for t in range(item, target + 1):
        dp[t] = dp[t] or dp[t - item]

Going down, dp[t - item] still holds the value from before this item. Going up, it may already include it.

Partition Equal Subset Sum counts down. Coin Change counts up. That is the only structural difference between them.

The twelve problems

#	Problem	The one insight
4.23.1	Climbing Stairs ★	Fibonacci — arrive from one below or two
4.23.2	Min Cost Climbing Stairs	The same, with min instead of +
4.23.3	House Robber ★	Take it or leave it; taking forces a skip
4.23.4	House Robber II ★	Split the circle into two lines
4.23.5	Longest Palindromic Substring ★	Expand from 2n − 1 centres, not DP
4.23.6	Palindromic Substrings ★	Every expansion step is one more palindrome
4.23.7	Decode Ways ★	The two-step recurrence with validity rules
4.23.8	Coin Change ★	Try every coin as the last one
4.23.9	Maximum Product Subarray ★	Carry the minimum too — a negative flips it
4.23.10	Word Break ★	Where does the last word start?
4.23.11	Longest Increasing Subsequence ★	tails holds best endings, not a subsequence
4.23.12	Partition Equal Subset Sum	0/1 knapsack — count the loop down

★ marks the Blind 75 subset.

The traps on this pattern

A wrong base case. Check the smallest input by hand. dp[0] = 1 for counting problems (the empty way) and dp[0] = 0 for cost problems.

Answering with dp[n-1] when the state is "ending at i". Take the maximum over the table.

Updating two rolling variables in the wrong order. Compute both from the same snapshot, or use simultaneous assignment.

The loop direction on an in-place array. Down for once, up for reusable.

Reaching for greedy without a proof. If you cannot prove it, write the DP.

What the interviewer will push on

"What does dp[i] mean?" In one English sentence, before any code.

"Why is this not greedy?" Give a counterexample. Volunteering it is stronger than being asked.

"Why does the loop run that direction?" Reuse or no reuse.

"Can you reduce the space?" Name which cells the recurrence reads and keep only those. Then note that reconstructing the actual answer needs the full table, which is what the space optimisation gives up.

"Can you do better than O(n^2)?" Sometimes — LIS drops to O(n \log n); palindromes drop to O(n) with Manacher's.

One thing to volunteer: state the state definition, the base cases and the fill order before writing a line of code. That is the whole method, and doing it out loud converts a hard problem into a mechanical one.

Recall

• 1-D DP when the state is one number and the answer is a count, an optimum, or a yes/no.
• The tell for DP over greedy: a choice now restricts choices later. Test greedy by hunting a counterexample for thirty seconds.
• "How did I get here?" produces the recurrence. Combine with + for counting, min/max for optimising, or for possibility.
• "Ending at i" versus "considering the first i" are different states — LIS needs the first and answers with max(dp); House Robber uses the second.
• Loop direction on a rolled array decides reuse. Down = each item once (0/1 knapsack). Up = reusable (Coin Change).
• Most wrong DP has a correct recurrence and a wrong base case — check the smallest input by hand.
• Space optimisation costs you the ability to reconstruct the answer; keep the table if you need the choices.
• Not everything filed under DP should be DP — palindromes are better by centre expansion.

Next: 4.23.1 Climbing Stairs — the smallest complete DP, shown in all four forms.