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

Dynamic Programming Memoization, Knapsack, LCS

Dynamic Programming Memoization, Knapsack, LCS is an important Data Structure topic because it shows up in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.

Focus on what problem Dynamic Programming Memoization, Knapsack, LCS solves, where developers usually make mistakes, and how to verify the result with output, behavior, or a small test.

A strong understanding of Dynamic Programming Memoization, Knapsack, LCS should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work.

Dynamic Programming Memoization Knapsack LCS should be studied as a practical Data Structure lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.

In the data-structure > dynamic-programming page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.

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 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;
}

DP vs Recursion vs Greedy

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
    }
}

DP vs Recursion vs Greedy

# 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)

DP vs Recursion vs Greedy

// 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;
}

0/1 Knapsack Problem

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 Problem

# 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 Problem

// 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;
}

Longest Common Subsequence (LCS)

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 (LCS)

# 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 (LCS)

// 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

Dynamic Programming Memoization Knapsack LCS normal path trace

1. Define the input for Dynamic Programming Memoization Knapsack LCS.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.

Dynamic Programming Memoization Knapsack LCS edge path trace

1. Try empty, missing, duplicate, or invalid data.
2. Identify where Dynamic Programming Memoization Knapsack LCS changes behavior.
3. Explain the safest correction.
4. Retest the normal path.

Key Takeaways

Explain the purpose of Dynamic Programming Memoization, Knapsack, LCS before memorizing syntax.
Run or trace one small Data Structure example and confirm the output.
Test one normal case, one edge case, and one mistake case for Dynamic Programming Memoization, Knapsack, LCS.
Write the rule in your own words after checking the example.
Connect Dynamic Programming Memoization, Knapsack, LCS to a real project scenario instead of treating it as an isolated definition.

Common Mistakes to Avoid

WRONG Memorizing Dynamic Programming Memoization Knapsack LCS without the situation where it is useful.

RIGHT Connect Dynamic Programming Memoization Knapsack LCS to a concrete Data Structure task.

Purpose makes syntax easier to recall.

WRONG Testing Dynamic Programming Memoization Knapsack LCS only with the perfect input.

RIGHT Include empty, missing, duplicate, incompatible, or failed cases when relevant.

Real bugs usually appear outside the perfect path.

WRONG Changing code before reading the visible symptom or error message.

RIGHT Inspect the output, state, configuration, or stack trace connected to Dynamic Programming Memoization Knapsack LCS.

Evidence keeps debugging focused.

WRONG Memorizing Dynamic Programming Memoization Knapsack LCS without the situation where it is useful.

RIGHT Connect Dynamic Programming Memoization Knapsack LCS to a concrete Data Structure task.

Purpose makes syntax easier to recall.

Practice Tasks

Modify the example so it handles a different input or condition.
Write one mistake related to Dynamic Programming Memoization, Knapsack, LCS, then fix it and explain the fix.
Summarize when to use Dynamic Programming Memoization, Knapsack, LCS and when another approach is better.
Write a small example that uses Dynamic Programming Memoization Knapsack LCS in a realistic Data Structure scenario.
Change one important value in the Dynamic Programming Memoization Knapsack LCS example and predict the result first.

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 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.

Previous Next

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