Dynamic Programming: when to spot it, explain it, and practice it
Dynamic programming becomes manageable when you stop memorizing formulas and start asking what state must be remembered so the rest of the problem looks the same.
Pattern coverage
200+
Best first move
State must have a clear meaning you can say in one sentence.
Common failure point
State meaning is fuzzy, so the recurrence becomes random.
When this pattern should come to mind
Checklist before you code
The solving flow that works well in interviews
Name the state in plain language.
List the decisions that can transition into the state.
Write base cases that match your state definition exactly.
Choose an iteration order that guarantees dependencies are ready.
Only then optimize space or constants.
Common variants
Linear DP
The next answer depends on a prefix or previous few positions.
Sequence DP
Two sequences or matching relationships define the state.
Decision DP
You choose whether to take, skip, merge, or split at each step.
Template preview
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
Classic problems with useful framing
#198
House Robber
The cleanest way to explain take-vs-skip state.
Choose non-adjacent houses to maximize stolen money.
#322
Coin Change
Great for transition completeness and impossible states.
Find the minimum number of coins needed to make up an amount.
#300
Longest Increasing Subsequence
Bridges classic DP and binary-search optimization.
Find the length of the longest strictly increasing subsequence.
#1143
Longest Common Subsequence
The canonical sequence-DP interview question.
Find the length of the longest common subsequence between two strings.
A more useful problem ladder for practice
This is not a random list. It is ordered to help candidates build recognition first, add key variants next, and then increase pressure with harder cases.
Foundation
#121 Best Time to Buy and Sell Stock
Find the maximum profit from one buy and one sell.
At each day the only historical information that matters is the minimum price seen before today.
Foundation
#5 Longest Palindromic Substring
Find the longest palindromic substring in a string.
A substring is a palindrome if its endpoints match and the inner substring is also a palindrome, with short substrings handled as base cases.
Variant depth
#53 Maximum Subarray
Find the contiguous subarray with the maximum sum.
At each position you only need the best subarray ending here, not every previous interval.
Variant depth
#62 Unique Paths
Count the number of ways to move from top-left to bottom-right in a grid.
The robot's path into a cell can only come from one of two predecessor cells.
Pressure test
#91 Decode Ways
Count the number of ways to decode a digit string.
The transition depends on whether the last one-digit and last two-digit segments form valid letters.
Pressure test
#152 Maximum Product Subarray
Find the contiguous subarray with the maximum product.
The current negative number can turn the previous minimum into the new maximum.
High-frequency mistakes
State meaning is fuzzy, so the recurrence becomes random.
Base cases do not match the state definition.
Transition misses one legal choice or double-counts two paths.
Space optimization is attempted before correctness is proven.
Recommended practice path
Start with linear DP like climbing stairs and house robber.
Move to sequence DP such as longest common subsequence.
Then add decision-heavy problems like coin change and decode ways.
Finish with interval or advanced state DP only after the basics feel natural.