How do you approach a DP problem you've never seen before?
DP is the most feared algo interview topic. A repeatable framework matters more than memorizing 50 problems.
Step 1: Identify overlapping subproblems + optimal substructure. If the problem can be expressed as "best of some smaller versions", DP applies.
Step 2: Define the state. What variables fully describe a subproblem? This is usually the hardest step.
Step 3: Write the transition. How do we get dp[i] from smaller states? Express as a recurrence.
Step 4: Set base cases and iteration order. Iterate small-to-large when children must be computed first.
Step 5: Optimize. Rolling array (O(n²) → O(n) space), change dimension, early exit. Do this AFTER it works.
I follow a fixed pipeline. First I ask: does picking or not-picking at step i recurse into the same shape of subproblem? If yes, DP. Then I nail down the state — for knapsack it's (item_index, remaining_capacity); for edit distance it's (i, j) pointing into both strings. Writing the transition forces me to articulate "what choice am I making at this state and how does it reduce to smaller states". Base cases fall out of the transition — wherever the recursion bottoms. I write it top-down with memoization first because it maps 1:1 to the recursive reasoning; I convert to tabulation only when I need to optimize space with rolling arrays. Most 'I don't know DP' anxiety comes from skipping step 2 — once the state is clean the transition almost writes itself.
Draw the recursion tree by hand for a tiny input — overlap visually screams "DP".
If you can't define state in one sentence, try a different state.
HireMe AI (即答侠) collects 12 archetype DP patterns (knapsack, LIS, interval, tree DP) so you recognize structure fast.
Top-down is easier to derive and handles sparse states better. Bottom-up is often faster (no recursion overhead) and enables space optimization.
When the optimal can be reached greedily, or when no overlap exists and plain recursion/divide-and-conquer suffices.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free