Dynamic Programming: A Practical Guide
From Confusion to Confidence in DP Problems
By Elizabeth, Founder
Why DP Feels Hard (And Why It Doesn't Have to Be)
Dynamic programming intimidates many developers, but it's really just optimized recursion. The key insight: if you're solving the same subproblems repeatedly, store their results.
This guide teaches you to recognize DP problems and solve them with a systematic approach that works in interviews.
When to Use Dynamic Programming
DP applies when a problem has these two properties:
1. Optimal Substructure
The optimal solution contains optimal solutions to subproblems. "Best way to get from A to C" = "Best A to B" + "Best B to C"
2. Overlapping Subproblems
You solve the same subproblems multiple times. Without caching, Fibonacci runs in O(2^n). With DP, it's O(n).
Interview tip: Words like "minimum," "maximum," "count ways," "longest," "shortest," or "is it possible" often signal DP.
The 5-Step DP Framework
Use this framework for every DP problem:
Step 1: Define the State
What does dp[i] (or dp[i][j]) represent? This is the hardest step. The state should capture everything needed to make decisions.
Step 2: Find the Recurrence
How does dp[i] relate to previous states? Express dp[i] in terms of dp[i-1], dp[i-2], etc.
Step 3: Identify Base Cases
What are the smallest subproblems with known answers? Usually dp[0] or dp[0][0].
Step 4: Determine Order
In what order should you fill the DP table? Dependencies matter. Usually left-to-right, top-to-bottom.
Step 5: Extract the Answer
Where is your final answer? Usually dp[n-1] or dp[n][m].
Pattern 1: Linear DP (1D Array)
The simplest form. State depends on previous elements in a sequence.
Example: Climbing Stairs
You can climb 1 or 2 steps. How many distinct ways to reach step n?
function climbStairs(n) {
// State: dp[i] = ways to reach step i
// Recurrence: dp[i] = dp[i-1] + dp[i-2]
// Base cases: dp[1] = 1, dp[2] = 2
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
// Time: O(n), Space: O(1) with rolling variablesExample: House Robber
Rob houses for max money, but can't rob adjacent houses.
function rob(nums) {
// State: dp[i] = max money robbing houses 0..i
// Choice at i: rob house i (+ dp[i-2]) or skip it (dp[i-1])
// Recurrence: dp[i] = max(nums[i] + dp[i-2], dp[i-1])
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = 0, prev1 = nums[0];
for (let i = 1; i < nums.length; i++) {
const curr = Math.max(nums[i] + prev2, prev1);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}Pattern 2: 2D Grid DP
State depends on row and column. Common for path-finding problems.
Example: Unique Paths
Count paths from top-left to bottom-right, moving only right or down.
function uniquePaths(m, n) {
// State: dp[i][j] = paths to reach cell (i, j)
// Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]
// Base: first row and column are all 1s
const dp = Array(m).fill(null).map(() => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n) - can optimize to O(n)Example: Minimum Path Sum
Find path with minimum cost from top-left to bottom-right.
function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
// Modify grid in-place (or use separate dp array)
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 && j === 0) continue;
else if (i === 0) grid[i][j] += grid[i][j - 1];
else if (j === 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}Pattern 3: String DP
Compare or transform strings. Usually 2D where dp[i][j] involves s1[0..i] and s2[0..j].
Example: Longest Common Subsequence
function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
// dp[i][j] = LCS of text1[0..i-1] and text2[0..j-1]
const dp = Array(m + 1).fill(null)
.map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}Pattern 4: Knapsack Problems
Select items with constraints to optimize value. The classic DP pattern.
0/1 Knapsack (Take or Leave)
function knapsack(weights, values, capacity) {
const n = weights.length;
// dp[i][w] = max value using items 0..i-1 with capacity w
const dp = Array(n + 1).fill(null)
.map(() => Array(capacity + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
// Don't take item i-1
dp[i][w] = dp[i - 1][w];
// Take item i-1 (if it fits)
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
);
}
}
}
return dp[n][capacity];
}
// Time: O(n * capacity), Space: O(n * capacity)Variants: Unbounded knapsack (unlimited items), coin change (ways to make amount), subset sum (can we hit target?).
Space Optimization: Rolling Array
When dp[i] only depends on dp[i-1], you don't need the full table. Use two rows (or even one row with careful ordering).
// 2D to 1D optimization for Unique Paths
function uniquePathsOptimized(m, n) {
const dp = Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1]; // dp[j] = above + left
}
}
return dp[n - 1];
}
// Space: O(m*n) → O(n)Top-Down vs Bottom-Up
Top-Down (Memoization)
- + Natural recursive thinking
- + Only computes needed states
- - Recursion stack overhead
- - Risk of stack overflow
Bottom-Up (Tabulation)
- + No recursion overhead
- + Easier space optimization
- - Must compute all states
- - Order can be tricky
Interview tip: Start with top-down (easier to write), then convert to bottom-up if asked about optimization.
Common Interview Problems by Pattern
Linear DP
Climbing Stairs, House Robber, Maximum Subarray, Coin Change, Longest Increasing Subsequence
Grid DP
Unique Paths, Minimum Path Sum, Dungeon Game, Maximal Square
String DP
LCS, Edit Distance, Longest Palindromic Substring, Word Break, Regular Expression Matching
Knapsack Variants
0/1 Knapsack, Coin Change (ways), Partition Equal Subset Sum, Target Sum
Practice Strategy
- Start with Climbing Stairs (simplest DP)
- Move to House Robber (decision at each step)
- Try Unique Paths (2D introduction)
- Tackle Coin Change (knapsack variant)
- Master LCS/Edit Distance (string DP)
Remember: DP mastery comes from recognizing patterns, not memorizing solutions. Each problem you solve adds to your pattern vocabulary.
Continue Learning
- Big O Notation Explained - Understand why DP reduces exponential to polynomial time
- Hash Maps: When and Why - Essential for memoization implementations
- Sliding Window Technique - Another optimization pattern to master
- Start Practicing - Apply DP patterns to real interview problems
Article Details
This guide is part of HireReady's interview prep library and is maintained to reflect current hiring practices.
Keep Reading
Trie Data Structure: Complete Interview Guide
Master the trie (prefix tree) for solving autocomplete, spell checking, and word search problems. Learn implementation, variations, and common interview patterns.
Read moreStack Pattern: Complete Interview Guide
Master stack patterns for coding interviews. Learn matching brackets, monotonic stack, expression evaluation, and common LeetCode problems.
Read moreBig O Notation Explained
Complete guide to Big O notation, algorithmic complexity, and performance analysis. Learn to calculate time and space complexity from code with real examples.
Read more