Module 09: Dynamic Programming — Frameworks, Patterns & Optimizations

Goal: Master identifying optimal substructure and overlapping subproblems, the 4-step transformation framework (Recursion $\to$ Memoization $\to$ Tabulation $\to$ Space Optimization), the 6 major DP categories (1D, Grid, Knapsack, LCS, LIS, Interval/Tree DP), and state optimizations.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 08.

📑 Table of Contents

The 4-Step Dynamic Programming Framework
Category 1: 1D Array DP & State Optimization
Category 2: 2D Grid DP & Matrix Paths
Category 3: Knapsack DP (0/1 vs Unbounded)
Category 4: Longest Common Subsequence (LCS) & String DP
Category 5: Longest Increasing Subsequence (LIS) in $O(N \log N)$
Category 6: Interval DP & Tree DP
6 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. The 4-Step Dynamic Programming Framework

Dynamic Programming applies when a problem exhibits:

Optimal Substructure: The optimal solution to the problem contains optimal solutions to its subproblems.
Overlapping Subproblems: The same subproblems are solved repeatedly in a naive recursion tree.

                    ┌──────────────────────────────────────────────┐
                    │      Step 1: Plain Recursion (Brute Force)   │
                    │   Define state f(n), base cases, recurrence  │
                    └──────────────────────┬───────────────────────┘
                                           │
                                           ▼
                    ┌──────────────────────────────────────────────┐
                    │    Step 2: Top-Down DP (Memoization Cache)   │
                    │  Add memo table to eliminate redundant work  │
                    └──────────────────────┬───────────────────────┘
                                           │
                                           ▼
                    ┌──────────────────────────────────────────────┐
                    │    Step 3: Bottom-Up DP (Tabulation Table)   │
                    │   Iterative loop filling table from base up  │
                    └──────────────────────┬───────────────────────┘
                                           │
                                           ▼
                    ┌──────────────────────────────────────────────┐
                    │     Step 4: Space Optimization (Variables)   │
                    │  Drop array dimension if only previous row/  │
                    │           state is needed (e.g. O(1))        │
                    └──────────────────────────────────────────────┘

2. Category 1: 1D Array DP & State Optimization

House Robber State Derivation

At house $i$, you can either:

Rob house $i$: Must not rob house $i-1$, gain $A[i] + dp[i-2]$.
Skip house $i$: Keep maximum loot from $dp[i-1]$.

$$dp[i] = \max(dp[i-1], , A[i] + dp[i-2])$$

// Space-Optimized O(1) Solution
int rob(const std::vector<int>& nums) {
    int prev2 = 0; // dp[i-2]
    int prev1 = 0; // dp[i-1]
    
    for (int num : nums) {
        int curr = std::max(prev1, num + prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

3. Category 2: 2D Grid DP & Matrix Paths

Problem: Number of paths from $(0,0)$ to $(M-1, N-1)$ moving only right and down. $$dp[r][c] = dp[r-1][c] + dp[r][c-1]$$

2D Table:                     Space Optimization (1D Array of size N):
┌─────┬─────┬─────┐          ┌─────┬─────┬─────┐
│  1  │  1  │  1  │   ===>   │  1  │  3  │  6  │  (dp[c] += dp[c-1])
├─────┼─────┼─────┤          └─────┴─────┴─────┘
│  1  │  2  │  3  │
├─────┼─────┼─────┤
│  1  │  3  │  6  │
└─────┴─────┴─────┘

int uniquePaths(int m, int n) {
    std::vector<int> dp(n, 1);
    for (int r = 1; r < m; ++r) {
        for (int c = 1; c < n; ++c) {
            dp[c] += dp[c - 1]; // dp[c] was top, dp[c-1] is left
        }
    }
    return dp[n - 1];
}
// Time: O(M * N), Space: O(N)

4. Category 3: Knapsack DP (0/1 vs Unbounded)

4.1 0/1 Knapsack (Each item used at most once)

Given weights $W$, values $V$, and capacity $C$: $$dp[i][w] = \max(dp[i-1][w], , V[i] + dp[i-1][w - W[i]])$$

1D Space Optimization Rule for 0/1 Knapsack: Iterate capacity $w$ in REVERSE (from $C$ down to $W[i]$) so each item is included at most once without overwriting values needed from the previous step!

std::vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; ++i) {
    for (int w = capacity; w >= weights[i]; --w) { // REVERSE LOOP!
        dp[w] = std::max(dp[w], values[i] + dp[w - weights[i]]);
    }
}

4.2 Unbounded Knapsack (Infinite supply of each item)

Iterate capacity $w$ FORWARD (from $W[i]$ up to $C$) so an item can be selected multiple times!

// Coin Change: Minimum coins to make amount
std::vector<int> dp(amount + 1, 1e9);
dp[0] = 0;
for (int coin : coins) {
    for (int w = coin; w <= amount; ++w) { // FORWARD LOOP!
        dp[w] = std::min(dp[w], 1 + dp[w - coin]);
    }
}

5. Category 4: Longest Common Subsequence (LCS) & String DP

Given strings $S_1$ and $S_2$:

If $S_1[i-1] == S_2[j-1]$: $dp[i][j] = 1 + dp[i-1][j-1]$
Else: $dp[i][j] = \max(dp[i-1][j], , dp[i][j-1])$

Edit Distance Operations (Levenshtein):
Insert:  dp[i][j-1] + 1
Delete:  dp[i-1][j] + 1
Replace: dp[i-1][j-1] + (S1[i-1] != S2[j-1])

6. Category 5: Longest Increasing Subsequence (LIS) in $O(N \log N)$

Patience Sorting maintains an array tails where tails[len] is the smallest tail value of all increasing subsequences of length len + 1.

#include <vector>
#include <algorithm>

int lengthOfLIS(const std::vector<int>& nums) {
    std::vector<int> tails;
    
    for (int x : nums) {
        // Binary search for first element >= x
        auto it = std::lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            tails.push_back(x); // Extend LIS length
        } else {
            *it = x; // Replace with smaller ending value
        }
    }
    return tails.size();
}
// Time Complexity: O(N log N)
// Space Complexity: O(N)

7. Category 6: Interval DP & Tree DP

7.1 Interval DP (Subarrays $[i, j]$)

Solve from smaller length intervals to larger length intervals:

for (int len = 1; len <= n; ++len) {
    for (int i = 0; i + len - 1 < n; ++i) {
        int j = i + len - 1;
        for (int k = i; k <= j; ++k) {
            // Split interval at pivot k
            dp[i][j] = std::max(dp[i][j], dp[i][k-1] + dp[k+1][j] + cost(i, k, j));
        }
    }
}

7.2 Tree DP (House Robber III)

Each node returns a pair: {loot_if_robbed, loot_if_not_robbed}. $$\text{rob}(\text{node}) = \text{node.val} + \text{not_rob}(\text{left}) + \text{not_rob}(\text{right})$$ $$\text{not_rob}(\text{node}) = \max(\text{rob}(\text{left}), \text{not_rob}(\text{left})) + \max(\text{rob}(\text{right}), \text{not_rob}(\text{right}))$$

8. 6 Practice Problems with Detailed Solutions

Problem 1: Edit Distance (LeetCode #72 - Medium/Hard)

Problem: Return the minimum number of operations (insert, delete, replace) to convert word1 to word2.

#include <string>
#include <vector>
#include <algorithm>

int minDistance(std::string word1, std::string word2) {
    int m = word1.size(), n = word2.size();
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    
    for (int i = 0; i <= m; ++i) dp[i][0] = i; // Delete all chars
    for (int j = 0; j <= n; ++j) dp[0][j] = j; // Insert all chars
    
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // No operation needed
            } else {
                dp[i][j] = 1 + std::min({
                    dp[i - 1][j],     // Delete
                    dp[i][j - 1],     // Insert
                    dp[i - 1][j - 1]  // Replace
                });
            }
        }
    }
    
    return dp[m][n];
}
// Time Complexity: O(M * N)
// Space Complexity: O(M * N) (can be reduced to O(N))

Problem 2: Partition Equal Subset Sum (LeetCode #416 - Medium)

Problem: Determine if array can be partitioned into two subsets with equal sum.

#include <vector>
#include <numeric>

bool canPartition(std::vector<int>& nums) {
    int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
    if (totalSum % 2 != 0) return false;
    
    int target = totalSum / 2;
    std::vector<bool> dp(target + 1, false);
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}
// Time Complexity: O(N * Target)
// Space Complexity: O(Target)

Problem 3: Coin Change (LeetCode #322 - Medium)

Problem: Return fewest coins needed to make up given amount.

#include <vector>
#include <algorithm>

int coinChange(std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int coin : coins) {
        for (int x = coin; x <= amount; ++x) {
            dp[x] = std::min(dp[x], dp[x - coin] + 1);
        }
    }
    
    return (dp[amount] > amount) ? -1 : dp[amount];
}
// Time Complexity: O(Coins * Amount)
// Space Complexity: O(Amount)

Problem 4: Burst Balloons (LeetCode #312 - Hard)

Problem: Burst balloons in order to maximize coins collected.

#include <vector>
#include <algorithm>

int maxCoins(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> arr(n + 2, 1);
    for (int i = 0; i < n; ++i) arr[i + 1] = nums[i];
    
    std::vector<std::vector<int>> dp(n + 2, std::vector<int>(n + 2, 0));
    
    for (int len = 1; len <= n; ++len) {
        for (int left = 1; left <= n - len + 1; ++left) {
            int right = left + len - 1;
            for (int k = left; k <= right; ++k) {
                int coins = arr[left - 1] * arr[k] * arr[right + 1];
                int total = coins + dp[left][k - 1] + dp[k + 1][right];
                dp[left][right] = std::max(dp[left][right], total);
            }
        }
    }
    
    return dp[1][n];
}
// Time Complexity: O(N^3)
// Space Complexity: O(N^2)

Problem 5: House Robber III (LeetCode #337 - Medium)

Problem: Binary tree where robbing parent prevents robbing direct children.

#include <algorithm>

struct TreeNode {
    int val;
    TreeNode *left, *right;
};

class SolutionHouseRobber3 {
private:
    struct RobResult {
        int robThis;
        int notRobThis;
    };

    RobResult dfs(TreeNode* root) {
        if (!root) return {0, 0};
        
        RobResult left = dfs(root->left);
        RobResult right = dfs(root->right);
        
        int robThis = root->val + left.notRobThis + right.notRobThis;
        int notRobThis = std::max(left.robThis, left.notRobThis) +
                         std::max(right.robThis, right.notRobThis);
                         
        return {robThis, notRobThis};
    }

public:
    int rob(TreeNode* root) {
        RobResult res = dfs(root);
        return std::max(res.robThis, res.notRobThis);
    }
};
// Time Complexity: O(N)
// Space Complexity: O(H) call stack

Problem 6: Decode Ways (LeetCode #91 - Medium)

#include <string>
#include <vector>

int numDecodings(std::string s) {
    if (s.empty() || s[0] == '0') return 0;
    
    int prev2 = 1; // dp[i-2]
    int prev1 = 1; // dp[i-1]
    
    for (size_t i = 1; i < s.length(); ++i) {
        int current = 0;
        int oneDigit = s[i] - '0';
        int twoDigits = std::stoi(s.substr(i - 1, 2));
        
        if (oneDigit >= 1 && oneDigit <= 9) current += prev1;
        if (twoDigits >= 10 && twoDigits <= 26) current += prev2;
        
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

9. Top 10 FAANG Interview Questions

Q1: What is the difference between Top-Down (Memoization) and Bottom-Up (Tabulation) DP?

Answer:

Top-Down: Recursive. Computes only the subproblems required to answer the root query (lazy evaluation). Downside: Call stack memory overhead and function call dispatch cost.
Bottom-Up: Iterative. Evaluates all subproblems systematically in topological dependency order. Advantage: Zero call stack overhead, better cache locality, easy to space-optimize.

Q2: Why must the inner loop run in reverse order for 1D space-optimized 0/1 Knapsack?

Answer: To prevent using the same item multiple times. When updating $dp[w] = \max(dp[w], V[i] + dp[w - W[i]])$, $dp[w - W[i]]$ must represent the state from the previous item $i-1$. If looped forward, $dp[w - W[i]]$ would have already been updated using item $i$, effectively turning it into an unbounded knapsack.

Q3: How do you identify whether a problem should be solved with DP vs Greedy?

Answer:

Greedy: A locally optimal choice at each step always leads to a globally optimal solution (Greedy Choice Property). Does not look back or reconsider choices.
DP: Future decisions depend on past choices, and local best decisions do NOT guarantee global optimality (e.g. 0/1 Knapsack with coin values ${1, 3, 4}$ making change for $6$: Greedy picks $4+1+1 = 3$ coins, DP finds $3+3 = 2$ coins).

Q4: How does Bitmask Dynamic Programming work?

Answer: Used when state involves subsets of a small collection (typically $N \le 20$). A single integer bitmask represents which items have been chosen/visited. State: $dp[\text{mask}][\text{last_node}]$. Transitions flip individual bits using bitwise operations (mask | (1 << next)). Total states: $2^N \cdot N$.

Q5: How do you reconstruct the actual path/items chosen in a DP solution?

Answer: Backtrack from the final state $(N, \text{Target})$ using the recurrence conditions: If $dp[i][w] == dp[i-1][w]$, item $i$ was not taken. Else if $dp[i][w] == dp[i-1][w - W[i]] + V[i]$, item $i$ was chosen; record item $i$ and transition to $w - W[i]$.

Q6: What is Divide and Conquer Optimization in DP?

Answer: Used for 2D DP recurrences of the form $dp[i][j] = \min_{k < j} (dp[i-1][k] + C(k, j))$. If the optimal split point $opt(i, j) \le opt(i, j+1)$ (monotonicity condition), computation time can be reduced from $O(K \cdot N^2)$ to $O(K \cdot N \log N)$.

Q7: What is Convex Hull Trick / Li Chao Tree optimization?

Answer: Optimizes DP transitions where state transitions resemble linear functions $y = m_k \cdot x + c_k$. Reduces finding the minimum/maximum line value from $O(N)$ to $O(\log N)$ or amortized $O(1)$.

Q8: How can state size be reduced in 2D DP when only the previous row is needed?

Answer: Use two 1D vectors (curr and prev) or a single vector with in-place updates. Reduces auxiliary space from $O(M \times N)$ to $O(\min(M, N))$.

Q9: What is Matrix Exponentiation for DP?

Answer: For linear recurrence relations (like Fibonacci or $K$-step linear transitions $dp[i] = \sum c_j dp[i-j]$), the transition can be written as matrix multiplication: $$\vec{V}_n = M^{n-1} \vec{V}_1$$ Using binary exponentiation, $M^n$ is computed in $O(K^3 \log N)$ time, allowing $N = 10^{18}$ to be solved in milliseconds!

Q10: How do you solve DP on Subtrees when a tree is undirected?

Answer: Pick an arbitrary root (e.g. node 0) and run DFS passing a parent parameter (dfs(u, parent)). This directs all edges away from root, converting the undirected tree into a DAG with clear child-parent subproblem dependencies.

09-dynamic-programming.md