How to Solve Dynamic Programming Problems
A practical framework for solving DP problems in interviews — identifying subproblems, state transitions, and optimization.
Why dynamic programming feels hard
Dynamic programming has a reputation as the hardest topic in coding interviews. Candidates often feel like each DP problem requires a completely new insight. But the truth is that DP follows a consistent process. Once you internalize the framework, even unfamiliar problems become approachable.
The core idea is simple: if a problem has overlapping subproblems and optimal substructure, you can break it into smaller pieces, solve each piece once, and combine the results. The challenge is learning to see this structure in different problem shapes.
The four-step DP framework
Step 1: Define the state
The state is what changes as you move through the problem. For the climbing stairs problem, the state is the current step number. For the knapsack problem, the state is the current item index and remaining capacity. A clear state definition is the most important part of solving a DP problem — everything else follows from it.
Ask yourself: what information do I need to make a decision at each step? That information is your state. Write it as dp[i] or dp[i][j] with a clear English description of what the value represents.
Step 2: Find the recurrence relation
The recurrence relation describes how the current state relates to previous states. For climbing stairs: dp[i] = dp[i-1] + dp[i-2] because you can reach step i from step i-1 or step i-2. For the knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) because you either skip item i or take it.
If you cannot find the recurrence, try solving the problem recursively first. The recursive calls reveal the recurrence naturally. Then check if different recursive paths solve the same subproblems — that confirms DP applies.
Step 3: Identify the base cases
Base cases are the smallest subproblems that you can solve directly without recursion. For climbing stairs: dp[0] = 1 (one way to stay at ground), dp[1] = 1. For longest common subsequence: dp[0][j] = 0 and dp[i][0] = 0. Missing or incorrect base cases are the most common source of bugs in DP solutions.
Step 4: Determine the iteration order
When converting to bottom-up, you need to fill the table in an order such that every state you depend on is already computed. For 1D problems, this usually means iterating left to right. For 2D problems, it is often row by row, left to right. If your recurrence depends on dp[i+1], iterate in reverse.
The five DP patterns
Linear DP
State depends on the previous one or two values. Examples: Fibonacci, climbing stairs, house robber, maximum subarray (Kadane's algorithm). These are the simplest DP problems and often can be space-optimized to O(1) since you only need the last few values.
Grid DP
State is a position in a 2D grid. Examples: unique paths, minimum path sum, edit distance, longest common subsequence. Fill the grid row by row. Many grid DP problems can be space-optimized to O(columns) using a single row plus one variable.
Knapsack DP
Choose items subject to a constraint. The 0/1 knapsack (each item used at most once) and unbounded knapsack (items can be reused) are the two main variants. Examples: subset sum, coin change, partition equal subset sum. The key is the two-dimensional state: item index and remaining capacity.
Interval DP
State is defined over a subarray or substring. Examples: longest palindromic subsequence, matrix chain multiplication, burst balloons. Iterate over interval length, then starting position. These problems often have O(n³) complexity.
State machine DP
Multiple states with transitions between them. Examples: best time to buy and sell stock (with cooldown or transaction limit), decode ways. Define one DP array per state and describe the transitions. This pattern looks intimidating but becomes mechanical once you draw the state diagram.
From recursion to bottom-up
The safest approach for interviews is to start with a recursive solution, then add memoization, and finally convert to bottom-up if time permits. Here is the progression for the coin change problem (minimum coins to make amount):
Recursive: for each coin, try using it and recurse on the remaining amount. This has exponential time complexity because of repeated subproblems.
Memoized: add a cache (dictionary or array) indexed by the remaining amount. Before recursing, check the cache. This brings complexity to O(amount × coins).
Bottom-up: create an array dp of size amount+1. Set dp[0] = 0. For each amount from 1 to target, try each coin and take the minimum. Same complexity, but no recursion overhead and no risk of stack overflow.
Common mistakes to avoid
Off-by-one errors in base cases and loop bounds cause most DP bugs. Always verify your solution against the smallest meaningful input before scaling up. Another common mistake is using the wrong iteration order — if your recurrence looks backward, you need to iterate forward, and vice versa.
When you practice DP problems, Phantom Coder can provide quick feedback on whether your approach is optimal, helping you iterate faster during preparation.
Practice problems by difficulty
Start with climbing stairs, house robber, and coin change. Move to longest common subsequence, edit distance, and longest increasing subsequence. Then tackle harder problems like burst balloons, regular expression matching, and word break II. Ten well-understood DP problems teach you more than fifty solved by following a solution.
Ready to ace your next interview?
Phantom Coder gives you real-time AI assistance, invisible to screen sharing.
Download for macOS — $99/mo