If you've been avoiding dynamic programming (DP) problems on LeetCode, you're not alone. DP has a reputation for being intimidating—problems seem to require magical insights, solutions look like they came from nowhere, and the "aha!" moment often feels out of reach.
But here's the truth: dynamic programming isn't magic. It's a systematic approach to solving problems by breaking them into smaller subproblems and storing results to avoid redundant calculations.
This guide will demystify DP from the ground up. By the end, you'll understand not just how to solve DP problems, but why the approach works and when to use it. We'll start with the fundamentals and build up to more complex patterns, with plenty of examples along the way.
Dynamic programming is a problem-solving technique that solves complex problems by:
The key insight is that many problems have overlapping subproblems. Without DP, you might solve the same subproblem multiple times, leading to exponential time complexity. With DP, you solve each subproblem once and reuse the result, dramatically improving efficiency.
There are two main approaches to implementing DP:
1. Top-Down (Memoization): Start with the original problem and recursively break it down, storing results as you go. This is often more intuitive.
2. Bottom-Up (Tabulation): Start with the smallest subproblems and build up to the solution. This is usually more space-efficient.
Both approaches solve the same problem; the choice is often a matter of preference and problem structure.
Not every problem needs DP. Here are the telltale signs that DP might be appropriate:
If solving the problem requires solving the same smaller problem multiple times, DP can help.
Example: In the Fibonacci sequence, calculating fib(5) requires fib(3) and fib(4), and fib(4) requires fib(3) again. Without memoization, you'd calculate fib(3) twice.
The optimal solution to the problem contains optimal solutions to its subproblems.
Example: In the "Coin Change" problem, the minimum coins needed for amount n is 1 plus the minimum coins needed for n - coin_value (for some coin). The optimal solution builds on optimal subproblem solutions.
Problems where you make a series of decisions and want to find the optimal sequence.
Example: "House Robber" — at each house, decide whether to rob it or skip it, maximizing total value.
Problems asking for:
Here's a systematic approach that works for most DP problems:
Ask yourself:
State is what you need to remember to solve a subproblem. It's usually expressed as:
Key Question: What information do I need to solve this subproblem?
The recurrence relation expresses how to compute dp[i] using previously computed values.
General Form: dp[i] = f(dp[i-1], dp[i-2], ..., dp[0])
Key Question: How can I express the current state in terms of previous states?
Base cases are the smallest subproblems that can be solved directly without recursion.
Key Question: What are the simplest cases I can solve immediately?
For bottom-up DP, determine the order in which to fill the DP table.
Key Question: Which subproblems need to be solved before others?
Write the code, then look for space optimization opportunities (e.g., if you only need the last few values, you might not need the entire array).
Let's start with the simplest DP problem: computing the nth Fibonacci number.
Problem: Calculate the nth Fibonacci number, where fib(0) = 0, fib(1) = 1, and fib(n) = fib(n-1) + fib(n-2).
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)Time Complexity: O(2^n) — exponential!
Why? We recalculate the same values repeatedly. For example, fib(5) calls fib(3) twice, fib(2) three times, etc.
def fib(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]Time Complexity: O(n) — each value calculated once
Space Complexity: O(n) — for the memo dictionary and call stack
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Time Complexity: O(n)
Space Complexity: O(n)
Since we only need the last two values:
def fib(n):
if n <= 1:
return n
prev2 = 0 # fib(0)
prev1 = 1 # fib(1)
for i in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1Time Complexity: O(n)
Space Complexity: O(1) — only storing two variables!
This is a classic DP problem that's essentially Fibonacci in disguise.
Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example: For n = 3, there are 3 ways: (1,1,1), (1,2), (2,1)
Step 1: Identify the Problem Type
Step 2: Define the State
Step 3: Find the Recurrence Relation
Step 4: Set Base Cases
Step 5: Implementation
def climbStairs(n: int) -> int:
if n <= 2:
return n
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Space-Optimized:
def climbStairs(n: int) -> int:
if n <= 2:
return n
prev2 = 1
prev1 = 1
for i in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1This introduces the concept of making decisions at each step.
Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. You cannot rob two adjacent houses. Determine the maximum amount of money you can rob.
Example:
Step 1: Identify the Problem Type
Step 2: Define the State
Step 3: Find the Recurrence Relation
At house i, we have two choices:
We want the maximum:
dp[i] = max(dp[i-1], nums[i] + dp[i-2])Step 4: Base Cases
Step 5: Implementation
def rob(nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[n-1]Space-Optimized:
def rob(nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, n):
current = max(prev1, nums[i] + prev2)
prev2 = prev1
prev1 = current
return prev1Understanding these patterns will help you recognize and solve DP problems faster:
Problems where the state depends on a single dimension (usually an index).
Examples: Fibonacci, Climbing Stairs, House Robber, Coin Change
Template:
dp = [0] * (n + 1)
dp[0] = base_case
for i in range(1, n + 1):
dp[i] = recurrence_relation(dp[i-1], dp[i-2], ...)
return dp[n]Problems involving grids or two parameters.
Examples: Unique Paths, Minimum Path Sum, Longest Common Subsequence
Template:
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize first row and column
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = recurrence_relation(dp[i-1][j], dp[i][j-1], ...)
return dp[m][n]Problems involving selecting items with constraints (weight, value, etc.).
Examples: 0/1 Knapsack, Coin Change, Partition Equal Subset Sum
Template:
dp = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
for i in range(1, len(items) + 1):
for w in range(1, capacity + 1):
if items[i-1].weight <= w:
dp[i][w] = max(
dp[i-1][w], # Don't take item
items[i-1].value + dp[i-1][w - items[i-1].weight] # Take item
)
else:
dp[i][w] = dp[i-1][w]
return dp[len(items)][capacity]Problems involving finding the longest subsequence with certain properties.
Examples: Longest Increasing Subsequence, Russian Doll Envelopes
Template:
dp = [1] * n # Each element is a subsequence of length 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]: # Or other condition
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Problems involving intervals or ranges.
Examples: Matrix Chain Multiplication, Palindrome Partitioning
Template:
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
for k in range(i, j):
dp[i][j] = min_or_max(
dp[i][j],
dp[i][k] + dp[k+1][j] + cost(i, k, j)
)This problem introduces the concept of unlimited choices.
Problem: You are given coins of different denominations and a total amount. Find the minimum number of coins needed to make that amount. You may use each coin unlimited times.
Example:
Step 1: Identify the Problem Type
Step 2: Define the State
Step 3: Recurrence Relation
For each amount i, try each coin:
dp[i] = min(dp[i], 1 + dp[i - coin]) for each coin if coin <= iStep 4: Base Case
Step 5: Implementation
def coinChange(coins: List[int], amount: int) -> int:
# Initialize with a large value (infinity)
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1Key Insight: We iterate through all amounts from 1 to amount, and for each amount, we try every coin. This ensures we find the minimum coins needed.
When your DP solution isn't working, check these common issues:
Symptom: Solution gives wrong answers for test cases.
Fix: Re-examine your logic. Draw out the decision tree or state transitions manually for a small example.
Symptom: Solution fails for edge cases (empty input, single element, etc.).
Fix: Explicitly handle all base cases before the main loop.
Symptom: Runtime errors when accessing dp[i-k] for negative indices.
Fix: Add bounds checking:
if i - k >= 0:
dp[i] = max(dp[i], dp[i-k] + value)Symptom: Getting 0 or unexpected values.
Fix: Initialize the DP array correctly. For minimization problems, use a large value. For maximization, use 0 or a small value.
Symptom: Solution works for some inputs but not others.
Fix: Ensure you're computing dependencies in the correct order. In bottom-up DP, compute smaller subproblems before larger ones.
To master DP, follow this progression:
Start with the recurrence relation — Don't jump to code. Explain the state and transition first.
Draw it out — Use a whiteboard to show the DP table filling up. This demonstrates understanding.
Mention optimization — After giving the O(n) space solution, mention that you could optimize to O(1) if only the last few values are needed.
Handle edge cases — Always check for empty inputs, single elements, and boundary conditions.
Test with examples — Walk through your solution with the given example to verify correctness.
Problem: Defining state with unnecessary dimensions.
Example: For "Climbing Stairs," you don't need dp[i][j] to track position and steps taken. dp[i] (position) is sufficient.
Fix: Start simple. Add dimensions only if necessary.
Problem: Trying greedy or other approaches when DP is more appropriate.
Fix: If you see overlapping subproblems and optimal substructure, try DP first.
Problem: Using dp[0] = 0 when it should be dp[0] = 1 (or vice versa).
Fix: Think carefully about what the base case represents. For counting problems, dp[0] is often 1 (one way to do nothing).
Problem: Returning dp[n] when you should return dp[n-1], or vice versa.
Fix: Be consistent with your indexing. Document whether indices are 0-based or 1-based.
When learning DP, having access to step-by-step hinting system can help you understand the recurrence relation without immediately seeing the solution. The key is getting guidance on state definition and transitions rather than the complete code.
For a structured approach to mastering DP along with other patterns, consider following a DSA learning path that introduces DP problems in a logical sequence, building complexity gradually.
Q: How do I know if a problem is a DP problem?
A: Look for overlapping subproblems (solving the same thing multiple times), optimal substructure (optimal solution contains optimal subproblem solutions), and optimization/counting questions. If you find yourself saying "if I knew the answer to a smaller version, I could solve this," it's likely DP.
Q: Should I use top-down (memoization) or bottom-up (tabulation)?
A: Top-down is often more intuitive and matches the problem structure. Bottom-up is usually more space-efficient and avoids stack overflow for large inputs. In interviews, either is fine, but mention that you could optimize space if needed.
Q: What's the difference between DP and divide-and-conquer?
A: Divide-and-conquer breaks problems into independent subproblems (no overlap). DP handles overlapping subproblems by storing results. Merge sort is divide-and-conquer; Fibonacci is DP.
Q: How do I find the recurrence relation?
A: Ask: "What decisions can I make at this step?" Then express the current state in terms of states you've already computed. For optimization, use min or max. For counting, use addition.
Q: Can every DP problem be space-optimized?
A: Not always, but many 1D DP problems can be optimized from O(n) to O(1) or O(k) if you only need the last k values. 2D DP problems can sometimes be optimized from O(m×n) to O(min(m,n)) if you only need the previous row.
Q: How do I handle DP problems with multiple constraints?
A: Add dimensions to your state. For example, if you have both a capacity constraint and a count constraint, use dp[i][capacity][count]. Start with the necessary dimensions and optimize later if possible.
Q: What if I can't figure out the recurrence relation?
A: Start with the base cases and work forward. Ask: "What's the simplest case?" Then: "If I know the answer for size n-1, how do I get the answer for size n?" Draw out examples manually.
Dynamic programming is a powerful technique that transforms exponential-time problems into polynomial-time solutions. The key to mastering DP is understanding the fundamental concepts:
Start with simple 1D problems like Fibonacci and Climbing Stairs to build intuition. Progress to decision-making problems like House Robber. Then tackle 2D problems and knapsack variants. With consistent practice, you'll develop pattern recognition that makes DP problems feel systematic rather than mysterious.
Remember: every expert was once a beginner. DP problems that seem impossible today will feel routine after you've solved 20-30 of them. The systematic framework outlined here will guide you through that journey.
The most important skill isn't memorizing solutions—it's recognizing when DP applies and knowing how to derive the recurrence relation from first principles. With that foundation, you can tackle new DP problems confidently in interviews and beyond.
Apply these techniques with LeetCopilot's AI-powered hints, notes, and mock interviews. Transform your coding interview preparation today.