Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Sections
Dynamic Programming: From Recursion to Optimization
A systematic approach to solving DP problems: from recognizing when to use DP, to formulating states, to writing clean bottom-up solutions. Covers 1D, 2D, and interval DP patterns.
Recognizing a DP Problem
DP applies when two conditions hold:
- Overlapping subproblems — the same subproblem is solved multiple times in recursion.
- Optimal substructure — the optimal solution to a problem contains optimal solutions to subproblems.
Signal words: 'count the number of ways', 'find the minimum cost', 'find the longest/shortest', 'can you reach X'. DP is NOT the right pattern if you can make a greedy choice that is always optimal.
5-Step DP Formulation
Define the state
What does dp[i] represent? Be precise. Example: dp[i] = minimum coins needed to make amount i. State definition is the hardest and most important step.
Identify base cases
What is the simplest instance of the problem? Example: dp[0] = 0 (0 coins needed for amount 0).
Write the recurrence
How does dp[i] relate to smaller subproblems? Example: dp[i] = min(dp[i - coin] + 1) for each coin ≤ i.
Determine order of computation
Bottom-up: compute from base cases up. Top-down: use memoization. Ensure each subproblem is solved before it's needed.
Extract the answer
The answer is often dp[n], but might be max(dp), or dp[n][m], depending on the problem.