Dynamic Programming solves problems with overlapping subproblems and optimal substructure. Four components: define state (what does dp[i] mean?), write the recurrence (dp[i] = f(dp[i-1], ...)), identify base cases, and determine evaluation order (top-down memoization or bottom-up table). Common problems: Fibonacci, 0/1 Knapsack, Coin Change, Edit Distance, Longest Increasing Subsequence.
Five classic DP problem patterns with their state definitions.
Spend 80% of the time defining dp[i] clearly. A wrong state definition leads to an unsolvable recurrence. dp[i] must encode all necessary context.
For 1D space-optimised Knapsack, iterate w from W down to weight[i]. Forward iteration would allow using item i multiple times.
Maintain a tails array where tails[i] = smallest tail of all increasing subsequences of length i+1. Binary search for each element.
Sign in to share your feedback and join the discussion.