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

What is Dynamic Programming?

Dynamic Programming (DP) is a method for solving optimization and counting problems by breaking them into smaller subproblems, solving each subproblem once, and storing its answer so it can be reused later.

DP is especially useful when a recursive solution would solve the same subproblems repeatedly. Instead of recomputing them again and again, DP saves the result and uses it whenever needed.

Two Key Properties of DP

A problem is a good candidate for dynamic programming when it has:

Optimal substructure: the optimal answer to the whole problem can be built from optimal answers to smaller subproblems.
Overlapping subproblems: the same smaller subproblems appear many times.

If subproblems do not overlap, divide-and-conquer may be more appropriate than dynamic programming.

Core Idea

The central idea of DP is:

Define a state that represents a smaller version of the problem.
Write a recurrence relation or transition to compute that state.
Set base cases.
Store answers in a tl-table or cache.
Build the final answer from the stored results.

Most DP problems become much easier once the state and transition are chosen correctly.

Memoization vs Tabulation

Approach	Direction	Main Idea	When Useful
Memoization	Top-down	Write recursion and cache results	When recurrence is natural recursively
Tabulation	Bottom-up	Fill tl-table from base cases upward	When evaluation order is clear

Memoization is often easier to write first because it follows the recursive structure of the problem. Tabulation is often more iterative and can avoid recursion overhead.

How to Think in DP

When designing a DP solution, ask these questions:

What exactly is the smaller subproblem?
What parameters fully describe that subproblem?
How can the answer for one state be built from earlier states?
What are the smallest states whose answers are already known?
Do I need only the answer value, or also the actual choices/path?

A large part of learning DP is learning how to define a good state.

General DP Template

A common DP workflow is:

Identify the state.
Find the recurrence relation.
Set base cases.
Choose memoization or tabulation.
Optionally reconstruct the chosen solution.
Optimize space if only previous rows/states are needed.

DP vs Greedy vs Backtracking

Feature	Dynamic Programming	Greedy	Backtracking
Main idea	Reuse solutions to overlapping subproblems	Make best local choice	Try choices and undo if needed
Optimality	Yes, if recurrence is correct	Only for suitable problems	Yes, if all valid cases explored
Typical cost	Moderate time and memory	Usually fast	Often exponential
Examples	Knapsack, LCS, edit distance	MST, Huffman, activity selection	N-Queens, subset sum search

0/1 Knapsack Problem

Given items with weights and values, and a knapsack capacity W, find the maximum value that can be carried. Each item can be used at most once.

This is a classic DP problem because for each item, we have two choices:

do not take the item, or
take the item if it fits.

So the state is often defined as: maximum value using first n items and capacity W.

0/1 Knapsack - Memoization and Tabulation

import java.util.Arrays;

public class Knapsack {

    static int[][] memo;

    // Memoization (Top-Down)
    static int knapsackMemo(int[] wt, int[] val, int capacity, int n) {
        if (n == 0 || capacity == 0) return 0;
        if (memo[n][capacity] != -1) return memo[n][capacity];

        if (wt[n - 1] > capacity) {
            memo[n][capacity] = knapsackMemo(wt, val, capacity, n - 1);
        } else {
            memo[n][capacity] = Math.max(
                knapsackMemo(wt, val, capacity, n - 1),
                val[n - 1] + knapsackMemo(wt, val, capacity - wt[n - 1], n - 1)
            );
        }
        return memo[n][capacity];
    }

    // Tabulation (Bottom-Up)
    static int knapsackDP(int[] wt, int[] val, int capacity) {
        int n = wt.length;
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                dp[i][w] = dp[i - 1][w];
                if (wt[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w],
                        val[i - 1] + dp[i - 1][w - wt[i - 1]]);
                }
            }
        }
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;
        int n = weights.length;

        memo = new int[n + 1][capacity + 1];
        for (int[] tl-row : memo) Arrays.fill(row, -1);

        System.out.println("Memoization: " + knapsackMemo(weights, values, capacity, n));
        System.out.println("Tabulation:  " + knapsackDP(weights, values, capacity));
    }
}

Why 0/1 Knapsack Is Not Greedy

In fractional knapsack, taking the best value-to-weight ratio first works because we are allowed to take fractions of items. In 0/1 knapsack, that rule may fail because taking one item can block a better combination of items later.

This is one of the most important examples for understanding why some problems need DP instead of greedy.

Longest Common Subsequence (LCS)

Given two strings, the Longest Common Subsequence problem asks for the longest sequence of characters that appears in both strings in the same order, but not necessarily contiguously.

The common DP state is: LCS length of prefixes s1[0..i-1] and s2[0..j-1].

Transition:

if the current characters match, add 1 to the answer of the smaller prefixes,
otherwise take the maximum by skipping one character from either string.

Longest Common Subsequence

public class LCS {

    static int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    static String lcsString(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        System.out.println(lcs("ABCBDAB", "BDCAB"));
        System.out.println(lcsString("ABCBDAB", "BDCAB"));
    }
}

Coin Change Problem

Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. This is a classic DP problem because the answer for amount x depends on smaller amounts such as x - coin.

State idea: dp[i] = minimum coins needed to make amount i.

Transition: for every coin, try using it as the last coin and update the best answer.

Coin Change - Minimum Coins

import java.util.Arrays;

public class CoinChangeDP {

    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) {
        int[] coins1 = {1, 5, 6, 9};
        System.out.println("Coins {1,5,6,9}, amount=11: " + coinChange(coins1, 11));

        int[] coins2 = {1, 2, 5};
        System.out.println("Coins {1,2,5}, amount=11: " + coinChange(coins2, 11));

        int[] coins3 = {2};
        System.out.println("Coins {2}, amount=3: " + coinChange(coins3, 3));
    }
}

Why Coin Change Is a Good DP Example

Coin change is important because it clearly shows that a greedy approach can fail. For coins {1, 5, 6, 9} and amount 11, greedy would choose 9 first, then 1 and 1, using 3 coins. But the optimal answer is 5 + 6 = 2 coins.

Space Optimization in DP

Some DP tables can be reduced from 2D to 1D if each tl-row depends only on the previous tl-row or a fixed small number of earlier states.

Examples:

Fibonacci can be reduced from O(n) space to O(1) space.
Coin change often uses a 1D array.
Knapsack can sometimes be optimized from 2D to 1D with careful loop ordering.

Space optimization is useful, but only after the full recurrence is clearly understood.

Reconstructing the Actual Answer

Sometimes the question asks for more than the optimal value. We may need the actual subsequence, path, or set of chosen items. In such cases, we often:

store parent/choice information, or
backtrack through the filled DP table.

The LCS example above shows reconstruction by backtracking through the table.

Common Dynamic Programming Problems

Problem	Typical State	Complexity
Fibonacci	dp[i] = ith Fibonacci number	O(n)
0/1 Knapsack	dp[i][w]	O(n x W)
LCS	dp[i][j]	O(m x n)
Coin Change	dp[amount]	O(n x amount)
Edit Distance	dp[i][j]	O(m x n)
Matrix Chain Multiplication	dp[i][j]	O(n^3)
Floyd-Warshall	dp[i][j] over intermediate vertices	O(V^3)

Common Mistakes

Choosing a state that does not fully describe the subproblem.
Writing the wrong recurrence relation.
Forgetting base cases.
Using tabulation in the wrong order.
Confusing 0/1 knapsack with fractional knapsack.
Optimizing space too early and breaking correctness.

When to Use Dynamic Programming

Use dynamic programming when:

the problem can be split into smaller overlapping subproblems,
the optimal answer depends on optimal answers to smaller parts,
naive recursion would repeat the same work many times,
you need an exact optimal answer rather than a locally good guess.

Key Takeaways

Dynamic programming stores answers to overlapping subproblems.
State, transition, and base cases are the heart of every DP solution.
Memoization is top-down; tabulation is bottom-up.
DP is often used for optimization, counting, and sequence problems.
A correct DP formulation is more important than memorizing tables.

Previous Next