Learn DSA Part 13: Dynamic Programming - Memoization, Knapsack, LCS and Interview Patterns

Dynamic programming (DP) has a reputation as the hardest interview topic, but it rests on one simple idea: if a recursive solution keeps solving the same subproblems, solve each one once and remember the answer. Once you learn to define a state and a transition, most DP problems turn into filling a table.

This is Part 13, the final part of the Learn DSA series. We cover when DP applies, memoization versus tabulation, a five-step recipe, and the classic families: 1D problems, knapsack and coin change, grid and string DP, and longest increasing subsequence. Code is in C++ and Java.

1. When to use dynamic programming

DP applies when a problem has:

• Overlapping subproblems: the same smaller problem appears many times in the recursion tree. Naive Fibonacci recomputes fib(n - 2) again and again, which is why it is exponential (Part 1).
• Optimal substructure: the best answer for the whole problem is built from best answers to subproblems.

Typical clues in the problem statement: "number of ways", "minimum or maximum cost", "longest or shortest", "is it possible", combined with choices at each step where greedy (Part 12) does not work.

2. A five-step recipe for any DP problem

1. State: define exactly what dp[i] (or dp[i][j]) means, in words. For example, "the maximum money robbed from the first i houses".
2. Transition: express a state using smaller states, usually by considering the last choice. "Either skip house i, or rob it and skip house i - 1."
3. Base cases: the smallest states you can fill directly.
4. Order: fill states so that every state's dependencies are computed first.
5. Answer: say which state holds the final result, such as dp[n] or the maximum over all states.

Time complexity is number of states x work per transition. Space can often be reduced when each state only looks back a fixed number of steps.

3. 1D DP: Climbing Stairs and House Robber

In House Robber you cannot rob two adjacent houses. Let dp[i] be the best total from the first i houses. Then dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]). Since each state uses only the previous two, two variables are enough: O(n) time and O(1) space.

// House Robber: max sum with no two adjacent houses. O(n) time, O(1) space
int rob(const vector<int>& nums) {
    int prev2 = 0, prev1 = 0;            // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = max(prev1, prev2 + x); // skip x, or take x
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

// House Robber: max sum with no two adjacent houses. O(n) time, O(1) space
static int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;            // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x); // skip x, or take x
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Climbing Stairs (ways[i] = ways[i - 1] + ways[i - 2]), Min Cost Climbing Stairs, Decode Ways and Maximum Subarray (Kadane's algorithm in Part 2) all follow the same 1D pattern.

4. Knapsack and Coin Change

In Coin Change, find the fewest coins that make an amount, with unlimited coins of each type. Let dp[a] be the minimum coins for amount a; for each coin c, dp[a] = min(dp[a], dp[a - c] + 1). This is the problem where greedy fails (Part 12).

// Coin Change: fewest coins to make amount, -1 if impossible. O(amount * coins)
int coinChange(const vector<int>& coins, int amount) {
    const int INF = amount + 1;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;                                    // base case
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] >= INF ? -1 : dp[amount];
}

// Coin Change: fewest coins to make amount, -1 if impossible. O(amount * coins)
static int coinChange(int[] coins, int amount) {
    int INF = amount + 1;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;                                    // base case
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] >= INF ? -1 : dp[amount];
}

• Unbounded (each item reusable, as in Coin Change): loop amounts upward so an item can be used again.
• 0/1 knapsack (each item at most once, as in Partition Equal Subset Sum): for each item, loop capacities downwards so the item is not reused within the same pass.
• Counting the number of ways (Coin Change II) uses the same table with += instead of min, looping coins in the outer loop so each combination is counted once.

5. 2D DP on grids and strings

When a problem involves two indices, such as positions in two strings or a row and a column, the state becomes dp[i][j]. Longest Common Subsequence is the template: if the current characters match, extend the diagonal; otherwise take the better of skipping a character from either string.

// Longest Common Subsequence. O(n * m) time and space
int longestCommonSubsequence(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a[i - 1] == b[j - 1])
                ? dp[i - 1][j - 1] + 1                    // characters match
                : max(dp[i - 1][j], dp[i][j - 1]);        // skip one of them
    return dp[n][m];
}

// Longest Common Subsequence. O(n * m) time and space
static int longestCommonSubsequence(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a.charAt(i - 1) == b.charAt(j - 1))
                ? dp[i - 1][j - 1] + 1                    // characters match
                : Math.max(dp[i - 1][j], dp[i][j - 1]);   // skip one of them
    return dp[n][m];
}

• Edit Distance: dp[i][j] = minimum operations to turn the first i characters of one word into the first j of the other, taking the minimum of insert, delete and replace.
• Unique Paths and Minimum Path Sum: each cell depends on the cell above and the cell to the left.
• Longest Palindromic Substring / Subsequence: interval DP over dp[i][j] for the substring from i to j, filled by increasing length.

A 2D table can usually be reduced to one or two rows, because each row depends only on the previous one.

6. Longest Increasing Subsequence and other families

LIS with dp[i] = length of the longest increasing subsequence ending at i takes O(n^2). A faster O(n log n) method keeps an array tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1, and places each number with binary search (Part 8). The length of tails is the answer.

Other DP families you will meet:

• DP on trees: compute values bottom-up from children, as in House Robber III or the diameter trick from Part 9.
• Bitmask DP: the state includes a set of used items stored as bits, for problems with n up to about 20.
• Stock problems: states such as "holding" and "not holding" a stock, with transitions between them each day.

Practice problems

These are classic LeetCode-style problems, listed roughly from easy to hard. For each one, write the state definition in a full sentence before coding.

1. Climbing Stairs (easy)
2. Min Cost Climbing Stairs (easy)
3. House Robber (medium)
4. Coin Change (medium)
5. Coin Change II (medium)
6. Longest Increasing Subsequence (medium)
7. Unique Paths (medium)
8. Longest Common Subsequence (medium)
9. Word Break (medium)
10. Partition Equal Subset Sum (medium, 0/1 knapsack)
11. Decode Ways (medium)
12. Longest Palindromic Substring (medium)
13. Edit Distance (medium)
14. Best Time to Buy and Sell Stock with Cooldown (medium)
15. Burst Balloons (hard, interval DP)