Dynamic Programming Memoization, Knapsack, LCS: Tutorial, Examples, FAQs & Interview Tips

What is Dynamic Programming?

Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems, solving each subproblem only once, and storing the results. It applies when a problem has two properties:

Optimal substructure - the optimal solution can be built from optimal solutions of subproblems
Overlapping subproblems - the same subproblems are solved multiple times in a naive recursive approach

Memoization vs Tabulation

Aspect	Memoization (Top-Down)	Tabulation (Bottom-Up)
Approach	Recursive + cache results	Iterative, fill tl-table from base cases
Order	Solves only needed subproblems	Solves all subproblems
Stack overhead	Yes - recursion stack	No - pure iteration
Code style	Closer to recursive thinking	More explicit, often faster
Space optimization	Harder	Easier (rolling array)

DP vs Recursion vs Greedy

Technique	When to Use	Example
Recursion	Problem has recursive structure, no overlapping subproblems	Tree traversal, Tower of Hanoi
Greedy	Local optimal choice leads to global optimum	Activity selection, Huffman coding
DP	Overlapping subproblems + optimal substructure	Knapsack, LCS, Coin Change

Fibonacci DP - Climbing Stairs - House Robber

#include <iostream>
#include <vector>
using namespace std;

// Fibonacci - bottom-up DP, O(n) time, O(1) space
long long fib(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b; b = c;
    }
    return b;
}

// Climbing Stairs - same as Fibonacci
// You can climb 1 or 2 steps. How many ways to reach step n?
int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b; a = b; b = c;
    }
    return b;
}

// House Robber - max sum with no two adjacent elements
// dp[i] = max(dp[i-1], dp[i-2] + nums[i])
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    int prev2 = nums[0], prev1 = max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int curr = max(prev1, prev2 + nums[i]);
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

int main() {
    cout << "fib(10) = " << fib(10) << endl;          // 55
    cout << "climbStairs(5) = " << climbStairs(5) << endl;  // 8
    vector<int> houses = {2, 7, 9, 3, 1};
    cout << "rob = " << rob(houses) << endl;            // 12 (2+9+1)
    return 0;
}

public class DP1D {

    static long fib(int n) {
        if (n <= 1) return n;
        long a = 0, b = 1;
        for (int i = 2; i <= n; i++) { long c = a + b; a = b; b = c; }
        return b;
    }

    static int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
        return b;
    }

    static int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1; prev1 = curr;
        }
        return prev1;
    }

    public static void main(String[] args) {
        System.out.println("fib(10) = " + fib(10));           // 55
        System.out.println("climbStairs(5) = " + climbStairs(5)); // 8
        System.out.println("rob = " + rob(new int[]{2,7,9,3,1})); // 12
    }
}

# Fibonacci - bottom-up DP, O(n) time, O(1) space
def fib(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Climbing Stairs - same recurrence as Fibonacci
def climb_stairs(n):
    if n <= 2: return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

# House Robber - max sum with no two adjacent elements
def rob(nums):
    if len(nums) == 1: return nums[0]
    prev2, prev1 = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2, prev1 = prev1, curr
    return prev1

print(f"fib(10) = {fib(10)}")              # 55
print(f"climb_stairs(5) = {climb_stairs(5)}")  # 8
print(f"rob = {rob([2, 7, 9, 3, 1])}")    # 12 (2+9+1)

// Fibonacci - bottom-up DP
function fib(n) {
    if (n <= 1) return n;
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) { [a, b] = [b, a + b]; }
    return b;
}

// Climbing Stairs
function climbStairs(n) {
    if (n <= 2) return n;
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) { [a, b] = [b, a + b]; }
    return b;
}

// House Robber
function rob(nums) {
    if (nums.length === 1) return nums[0];
    let prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        const curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

console.log("fib(10) =", fib(10));              // 55
console.log("climbStairs(5) =", climbStairs(5)); // 8
console.log("rob =", rob([2, 7, 9, 3, 1]));     // 12

0/1 Knapsack Problem

Given n items each with a weight and value, and a knapsack of capacity W, find the maximum value you can carry. Each item can be taken at most once. This is a classic 2D DP problem: dp[i][w] = max value using first i items with capacity w.

0/1 Knapsack - O(n * W) DP

#include <iostream>
#include <vector>
using namespace std;

// 0/1 Knapsack - O(n*W) time, O(W) space (1D optimization)
int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < n; i++) {
        // Traverse right to left to avoid using item twice
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> weights = {1, 3, 4, 5};
    vector<int> values  = {1, 4, 5, 7};
    int W = 7;
    cout << "Max value: " << knapsack(weights, values, W) << endl;  // 9
    return 0;
}

public class Knapsack {

    static int knapsack(int[] weights, int[] values, int W) {
        int n = weights.length;
        int[] dp = new int[W + 1];
        for (int i = 0; i < n; i++) {
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values  = {1, 4, 5, 7};
        System.out.println("Max value: " + knapsack(weights, values, 7));  // 9
    }
}

# 0/1 Knapsack - O(n*W) time, O(W) space
def knapsack(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # right to left
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
print("Max value:", knapsack(weights, values, 7))  # 9

// 0/1 Knapsack - O(n*W) time, O(W) space
function knapsack(weights, values, W) {
    const n = weights.length;
    const dp = new Array(W + 1).fill(0);
    for (let i = 0; i < n; i++) {
        for (let w = W; w >= weights[i]; w--) {  // right to left
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

const weights = [1, 3, 4, 5];
const values  = [1, 4, 5, 7];
console.log("Max value:", knapsack(weights, values, 7));  // 9

Longest Common Subsequence (LCS)

LCS and Coin Change - Classic 2D and 1D DP

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Longest Common Subsequence - O(m*n) time and space
int lcs(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i-1] == b[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];
}

// Coin Change - minimum coins to make amount
// dp[i] = min coins to make amount i
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) dp[i] = min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    cout << "LCS: " << lcs("abcde", "ace") << endl;  // 3 ("ace")
    vector<int> coins = {1, 5, 6, 9};
    cout << "Coin change 11: " << coinChange(coins, 11) << endl;  // 2 (5+6)
    return 0;
}

import java.util.Arrays;

public class DP2D {

    static int lcs(String a, String b) {
        int m = a.length(), n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i-1) == b.charAt(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];
    }

    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println("LCS: " + lcs("abcde", "ace"));              // 3
        System.out.println("Coin change: " + coinChange(new int[]{1,5,6,9}, 11)); // 2
    }
}

# Longest Common Subsequence - O(m*n)
def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i-1] == b[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]

# Coin Change - minimum coins to make amount
def coin_change(coins, amount):
    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], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

print("LCS:", lcs("abcde", "ace"))              # 3 ("ace")
print("Coin change:", coin_change([1,5,6,9], 11))  # 2 (5+6)

// Longest Common Subsequence - O(m*n)
function lcs(a, b) {
    const m = a.length, n = b.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 (a[i-1] === b[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];
}

// Coin Change - minimum coins to make amount
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

console.log("LCS:", lcs("abcde", "ace"));               // 3
console.log("Coin change:", coinChange([1,5,6,9], 11));  // 2

Previous Next

Key Takeaways

Dynamic Programming solves problems by breaking them into overlapping subproblems and storing results.
Two approaches: Top-down (memoization - recursion + cache) and Bottom-up (tabulation - iterative).
A problem is suitable for DP if it has: optimal substructure + overlapping subproblems.
Always identify the state (what changes between subproblems) and the recurrence relation.
Space optimization: many DP problems only need the previous row/value - reduce O(n^2) space to O(n).
Classic DP problems: Fibonacci, 0/1 Knapsack, Longest Common Subsequence, Coin Change, Edit Distance.
Tabulation is usually faster than memoization due to no recursion overhead.

Frequently Asked Questions

What is the difference between memoization and tabulation?

Memoization (top-down): recursive approach that caches results of subproblems. Tabulation (bottom-up): iterative approach that fills a tl-table from base cases up. Tabulation is usually faster; memoization is easier to implement.

How do I identify if a problem can be solved with DP?

Look for: 1) Optimal substructure - optimal solution contains optimal solutions to subproblems. 2) Overlapping subproblems - same subproblems are solved multiple times. Common patterns: counting ways, min/max value, yes/no feasibility.

What is the Coin Change problem?

Given coins and a target amount, find the minimum number of coins to make the amount. DP solution: dp[i] = min coins for amount i. Recurrence: dp[i] = min(dp[i], dp[i-coin]+1) for each coin. Time: O(amount × coins).

What is the difference between DP and greedy algorithms?

Greedy makes the locally optimal choice at each step without reconsidering. DP considers all possibilities and stores results. Greedy is faster but does not always give the optimal solution. DP always gives optimal but uses more memory.