Dynamic Programming (DP) — Complete Guide

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem once, and storing the result to avoid redundant computation.

DP is the most asked topic in FAANG interviews — Google, Amazon, Microsoft, Meta. Problems like "minimum cost path", "longest increasing subsequence", or "number of ways to climb stairs" all use DP.

Two properties that signal a DP problem:

1. Optimal Substructure: The optimal answer to the main problem can be built from optimal answers to smaller subproblems.
2. Overlapping Subproblems: The same subproblems are solved multiple times in a naive recursive approach.

If only property 1 holds (no overlapping), it's a greedy problem. If both hold, use DP.

How to Identify a DP Problem

Ask yourself these questions:

• "Count the number of ways to..." → DP
• "Find the minimum/maximum..." → DP
• "Is it possible to..." → DP
• "Find the longest/shortest..." → DP
• Does the problem involve choices at each step (include/exclude, move left/right/diagonal)? → DP

Non-DP signals: Single pass, no repeated choices, greedy works → usually not DP.

Two Approaches to DP

Top-Down (Memoization)

Start with the original problem, break it into subproblems recursively, and cache results.

solve(n) = already solved? return cache[n] : compute and cache

• ✅ Easy to write (natural recursive thinking)
• ❌ Function call overhead, potential stack overflow

Bottom-Up (Tabulation)

Start from the smallest subproblem, fill a table iteratively up to the original problem.

dp[0] = base case
dp[1] = base case
dp[i] = computed from dp[i-1], dp[i-2], etc.

• ✅ No recursion overhead, faster in practice
• ✅ Can often optimize space (rolling array)
• ❌ Slightly harder to derive the recurrence

Solved Problem 1: Fibonacci Number 🟢 Easy

Transition from Naive → Memoized → Tabulated → Space-Optimized

The Fibonacci sequence is the perfect first DP example. F(n) = F(n-1) + F(n-2)

Naive Recursion — O(2ⁿ) Time ❌

javascript
function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);  // recomputes same values many times!
}

Call tree for fib(5):
              fib(5)
           /         \
        fib(4)       fib(3)
        /    \       /    \
     fib(3) fib(2) fib(2) fib(1)
     ...
fib(3) computed TWICE, fib(2) computed THREE times! → exponential waste

Top-Down: Memoization — O(N) Time, O(N) Space ✅

javascript
function fib(n, memo = {}) {
    if (n in memo) return memo[n];   // already computed!
    if (n <= 1) return n;
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

console.log(fib(50));  // instant — without memo this would take forever

Bottom-Up: Tabulation — O(N) Time, O(N) Space ✅

javascript
function fib(n) {
    if (n <= 1) return n;
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

Space-Optimized — O(N) Time, O(1) Space 🚀

javascript
function fib(n) {
    if (n <= 1) return n;
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Key Insight: We only need the last two values, not the full array. This reduces space from O(N) to O(1).

Solved Problem 2: Climbing Stairs 🟢 Easy

Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you climb to the top?

Examples:

n=2: [1+1, 2] → 2 ways
n=3: [1+1+1, 1+2, 2+1] → 3 ways
n=4: 5 ways
n=5: 8 ways

Pattern Recognition: Notice the pattern: 2, 3, 5, 8... This is Fibonacci! ways(n) = ways(n-1) + ways(n-2).

Why? To reach step n, you came either from step n-1 (by climbing 1 step) or from step n-2 (by climbing 2 steps). So total = sum of ways to reach those.

DP Recurrence: dp[i] = dp[i-1] + dp[i-2]
Base Cases: dp[1] = 1, dp[2] = 2

javascript
function climbStairs(n) {
    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;
}

console.log(climbStairs(5));  // 8
console.log(climbStairs(10)); // 89

Time: O(N) Space: O(1)

Solved Problem 3: 0/1 Knapsack 🟡 Medium

Problem: Given n items each with a weight and value, and a bag with capacity W, select items to maximize total value without exceeding the weight limit. Each item can be picked at most once (0/1 — either include or exclude).

Example:

Items:    [(weight=2, value=6), (weight=2, value=10), (weight=3, value=12)]
Capacity: W = 5

Best choice: item 2 (w=2,v=10) + item 3 (w=3,v=12) = total weight 5, value 22

DP State: dp[i][w] = maximum value using first i items with capacity w

Recurrence:

For each item i, weight[i], value[i]:
  If weight[i] > w: can't include item → dp[i][w] = dp[i-1][w]
  Else: max(exclude item, include item)
       = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

DP Table Walkthrough (capacity W=5):

Items: w=[2,2,3], v=[6,10,12]

       w=0  w=1  w=2  w=3  w=4  w=5
i=0:    0    0    0    0    0    0   (no items)
i=1:    0    0    6    6    6    6   (item1: w=2,v=6)
i=2:    0    0   10   10   16   16   (item2: w=2,v=10)
i=3:    0    0   10   12   16   22   (item3: w=3,v=12)

Answer: dp[3][5] = 22 ✅

JavaScript Solution:

javascript
function knapsack(weights, values, W) {
    const n = weights.length;
    // dp[i][w] = max value using first i items with capacity w
    const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= W; w++) {
            // Option 1: Don't include item i
            dp[i][w] = dp[i - 1][w];

            // Option 2: Include item i (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][W];
}

console.log(knapsack([2, 2, 3], [6, 10, 12], 5)); // 22

Space-Optimized (1D DP):

javascript
function knapsack1D(weights, values, W) {
    const dp = new Array(W + 1).fill(0);

    for (let i = 0; i < weights.length; i++) {
        // Iterate W backwards to prevent using item i twice
        for (let w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }

    return dp[W];
}

Time: O(N × W) Space: O(N × W) or O(W) optimized

Solved Problem 4: Longest Common Subsequence (LCS) 🟡 Medium

Problem: Given two strings text1 and text2, return the length of their Longest Common Subsequence (LCS). A subsequence is a sequence derived by deleting some characters without changing relative order.

Example:

text1 = "abcde"
text2 = "ace"
LCS = "ace" (length 3)

text1 = "abc"
text2 = "abc"
LCS = "abc" (length 3)

text1 = "abc"
text2 = "def"
LCS = "" (length 0, nothing in common)

DP State: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]

Recurrence:

If text1[i-1] == text2[j-1]: characters match!
    dp[i][j] = dp[i-1][j-1] + 1
Else: skip one character from either string
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2D DP Table for "abcde" and "ace":

     ""  a  c  e
""  [ 0  0  0  0 ]
a   [ 0  1  1  1 ]   'a'=='a' → dp[0][0]+1=1
b   [ 0  1  1  1 ]   'b'!='c' → max(1,1)=1
c   [ 0  1  2  2 ]   'c'=='c' → dp[1][1]+1=2
d   [ 0  1  2  2 ]   'd'!='e' → max(2,2)=2
e   [ 0  1  2  3 ]   'e'=='e' → dp[3][2]+1=3

LCS length = 3 ✅

JavaScript Solution:

javascript
function longestCommonSubsequence(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = Array.from({ length: m + 1 }, () => new 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;  // characters match
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);  // skip one
            }
        }
    }

    return dp[m][n];
}

console.log(longestCommonSubsequence("abcde", "ace"));  // 3
console.log(longestCommonSubsequence("abc", "abc"));    // 3
console.log(longestCommonSubsequence("abc", "def"));    // 0

Python Solution:

python
def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Time: O(M × N) Space: O(M × N) or O(N) with rolling array

Solved Problem 5: Coin Change 🟡 Medium

Problem: Given an array of coin denominations and a target amount, find the minimum number of coins needed to make up that amount. You can use each coin an unlimited number of times. Return -1 if impossible.

Example:

coins = [1, 5, 6, 9], amount = 11

Greedy (wrong): 9 + 1 + 1 = 3 coins ← greedy picks 9 first
DP (correct):   6 + 5 = 2 coins ← optimal!

Why greedy fails: picking the largest coin first doesn't always minimize count.

DP Recurrence: dp[i] = minimum coins to make amount i

dp[0] = 0           (0 coins needed for amount 0)
dp[i] = min over all coins c where c <= i:
        dp[i - c] + 1   (use coin c once, then solve for i-c)

Table for coins=[1,5,6,9], amount=11:

dp[0]  = 0
dp[1]  = dp[0]+1 = 1    (use coin 1)
dp[5]  = dp[0]+1 = 1    (use coin 5)
dp[6]  = dp[0]+1 = 1    (use coin 6)
dp[9]  = dp[0]+1 = 1    (use coin 9)
dp[10] = dp[5]+1 = 2    (use coin 5, then dp[5]=1)
dp[11] = dp[5]+1 = 2    (use coin 6, then dp[5]=1) ← minimum!
         or dp[6]+1=2   (use coin 5, then dp[6]=1)

JavaScript Solution:

javascript
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;  // base case: 0 coins for amount 0

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i && dp[i - coin] !== Infinity) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log(coinChange([1, 5, 6, 9], 11));  // 2
console.log(coinChange([2], 3));             // -1 (impossible)
console.log(coinChange([1, 2, 5], 11));      // 3 (5+5+1)

C++ Solution:

cpp
#include <vector>
#include <algorithm>
#include <climits>

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

Time: O(amount × number of coins) Space: O(amount)

Solved Problem 6: House Robber 🟡 Medium

Problem: You are a professional robber planning to rob houses along a street. Each house has some money stashed. Adjacent houses have security systems — if two adjacent houses are robbed, the alarm triggers. Find the maximum amount you can rob without alerting the police.

Example:

[2, 7, 9, 3, 1]
Can't take adjacent:
Option A: 2 + 9 + 1 = 12
Option B: 7 + 3 = 10
Option C: 2 + 9 = 11
Option D: 7 + 1 = 8
Best: 2 + 9 + 1 = 12 ✅

DP Recurrence: dp[i] = max money robbing houses 0..i

At house i: two choices:
  1. Rob house i: dp[i] = dp[i-2] + nums[i]  (skip adjacent i-1)
  2. Skip house i: dp[i] = dp[i-1]

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

From O(N) Space → O(1) Space:

javascript
function rob(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let prev2 = 0;           // dp[i-2]
    let prev1 = 0;           // dp[i-1]

    for (const num of nums) {
        const curr = Math.max(prev1, prev2 + num);
        prev2 = prev1;
        prev1 = curr;
    }

    return prev1;
}

console.log(rob([2, 7, 9, 3, 1]));  // 12
console.log(rob([1, 2, 3, 1]));      // 4 (1+3)
console.log(rob([2, 1, 1, 2]));      // 4 (2+2)

Time: O(N) Space: O(1)

DP Pattern Reference

Common DP Mistakes

1. Wrong base case: The most common bug — missing dp[0] or dp[1] initialization causes incorrect results for all larger values.

2. Wrong iteration order: For unbounded knapsack (items can be reused), iterate w from 0 → W (forward). For 0/1 knapsack (each item once), iterate w from W → 0 (backward). Mixing these allows double-counting.

3. Using global/shared arrays carelessly: In top-down memoization, make sure each unique subproblem maps to a unique cache key. 2D problems often need (i, j) as key, not just i.

4. Greedy trap: If the problem says "minimum coins" or "maximum value", don't assume greedy works. Test with a counterexample like coins=[1,5,6,9], amount=11 — greedy gives 3, DP gives 2.

5. Off-by-one in string DP: When dp[i][j] represents strings of length i and j, the characters accessed are s1[i-1] and s2[j-1]. This 1-indexed shift trips up many beginners.

Frequently Asked Questions

Q: How do I identify the DP state and transition?
A: The state represents "what information do I need to answer this subproblem?" For linear problems it's usually the current index. For 2D problems, it's two indices (position in two strings, or row/col in a grid). The transition comes from asking "if I know the answer to smaller subproblems, how do I build the answer for the current one?" Write the recurrence in plain English first, then code it.

Q: When does greedy work and when do I need DP?
A: Greedy works when the locally optimal choice at each step leads to a globally optimal solution — this must be provable. Classic greedy problems: activity selection, Huffman coding, minimum spanning tree. DP is needed when greedy fails — usually when the optimal choice depends on future choices (knapsack, coin change with non-unit coins). If in doubt, try to construct a counterexample for greedy — if you can, use DP.

Q: What is the difference between memoization and tabulation?
A: Both achieve the same result (O(N) complexity for Fibonacci vs O(2^N) naive). Memoization (top-down) starts from the original problem, recurses down, and caches results. Easy to write but has function call overhead and potential stack overflow. Tabulation (bottom-up) fills a table iteratively from base cases up. More efficient in practice, no stack issues, and easier to apply space optimization.

Q: How do I optimize DP space from O(N²) to O(N)?
A: Examine whether dp[i][j] only depends on the previous row (dp[i-1][...]). If so, maintain only two rows (current and previous) or even just one row updated in the right order. For 0/1 knapsack, iterating the weight dimension backwards on a single 1D array achieves O(W) space from O(N×W).

Q: What is the time complexity of DP solutions?
A: Generally O(number of states × cost per state). For 1D DP with N states and O(1) transition: O(N). For 2D DP with M×N states: O(M×N). For knapsack with N items and capacity W: O(N×W). The "number of states" is the size of your DP table.