How to See a DP Problem

"The mechanics of DP are easy — cache a recurrence. The real skill is two things: noticing 'this is a DP' in the first place, and nailing down what the state should be. Master those and DP stops being scary."

The Recognition Signals

Certain problem phrasings should make 'dynamic programming' light up in your head:

'Count the number of ways' to do something (paths through a grid, ways to decode a string, ways to make change).
'Minimize / maximize' over a sequence of choices (fewest coins, max loot, longest subsequence, lowest cost path).
'Can you partition / select / arrange' to satisfy a constraint (subset sum, knapsack).
A natural recursion exists, but it recomputes the same subproblems (overlapping) — the loudest signal of all.
Greedy is tempting but gives wrong answers — like coin change, where 'take the biggest coin' fails. When greed breaks, DP is often the fix.

The Five-Step Framework

Once you suspect DP, design it in five steps — and the first is the one that matters:

Define the state. Finish the sentence 'dp[...] = the answer to ___.' This is the hard step; get it right and the rest is mechanical, get it wrong and nothing works.
Write the transition. Express dp[state] in terms of smaller states — the recurrence.
Identify base cases. The smallest states you can answer directly.
Choose the order. Top-down (memoize the recursion) or bottom-up (tabulate). Either works.
Optimize space if needed (keep only the cells still referenced).

Steps 2–5 are routine once step 1 is solid. The entire difficulty of DP concentrates in defining the state — which is why 'write the sentence for dp first' has been the through-line of this whole track.

DP recipe: (1) define the state — the answer dp[...] represents, the hard part; (2) write the transition from smaller states; (3) base cases; (4) order (memoize or tabulate); (5) optimize space. Signals to reach for DP: 'count the ways', 'optimize over choices', overlapping recursion, or greedy that fails.

Greedy's Failure Is DP's Cue

A counterexample disproves that particular greedy rule; it does not prove DP is the only alternative. Coin change with {1,3,4} and amount 6 is a case where amount-state DP works well. For another problem, a different greedy rule, graph algorithm, or search method may be right, so verify overlap and state structure separately.

Pippa's Confession

For ages I'd stare at a DP problem and freeze, trying to picture the whole table at once. Dad cut it down to one instruction: "Don't draw the table. Just finish this sentence: dp of i comma j equals the answer to what?" The moment I could state what one cell meant, the transition wrote itself. Every DP I've ever gotten stuck on was a state I hadn't defined clearly — never a caching problem, always a 'what am I even computing?' problem.

Code

Recognize → define state → transition → base → order·python

# A worked recognition: 'count the number of unique paths' through a grid,
# moving only right or down. The phrase 'count the ways' screams DP.

# STEP 1 - STATE: dp[i][j] = number of paths from (0,0) to cell (i,j).
# STEP 2 - TRANSITION: you reach (i,j) from above (i-1,j) or left (i,j-1).
#          dp[i][j] = dp[i-1][j] + dp[i][j-1].
# STEP 3 - BASE CASES: the top row and left column have exactly 1 path each.
# STEP 4 - ORDER: fill row by row (each cell needs up & left, already done).
def unique_paths(rows, cols):
    dp = [[1] * cols for _ in range(rows)]   # base cases: edges are all 1
    for i in range(1, rows):
        for j in range(1, cols):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]   # the transition
    return dp[rows-1][cols-1]

print(unique_paths(3, 3))   # 6 paths through a 3x3 grid
# Notice: once the STATE sentence ('paths to (i,j)') was clear, every other
# step fell out mechanically. The state definition is the whole battle.

Exercise

Apply the five-step framework to 'decode ways': a string of digits where 1→A … 26→Z, count how many ways it can be decoded (e.g. '12' → 'AB' or 'L', so 2). Define the state dp[i] in a sentence, write the transition (consider decoding one digit vs two digits), and state the base case. You don't have to code it — just design it.

Hint

State: dp[i] = number of ways to decode the first i characters. Transition: dp[i] = dp[i-1] (if s[i-1] is a valid single digit 1-9) + dp[i-2] (if s[i-2:i] is a valid two-digit 10-26). Base: dp[0] = 1 (empty string, one way). The state sentence makes the two-way add obvious.

The Recognition Signals

The Five-Step Framework

Greedy's Failure Is DP's Cue

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0