C++ In Practice - Dynamic Programming

Dynamic Programming (C++11 Deep Dive)

In C++11, Dynamic Programming is primarily an exercise in managing std::vector efficiently. Unlike Python or JavaScript, C++ gives you strict control over memory allocation, which is crucial because DP tables can grow large (O(N^2) space).

STL Tools for DP

Component	C++ Tool	Why?
The Table	std::vector<int>	Dynamic sizing, contiguous memory (cache friendly).
2D Table	std::vector<std::vector<int>>	Easy syntax, though slightly fragmented memory.
Optimization	std::array<int, N>	Use if state size is small and fixed at compile time (e.g., constant alphabet size).
Transitions	std::max, std::min	Highly optimized, branchless assembly instructions on modern CPUs.
Binary Search	std::lower_bound	Essential for O(N \log N) LIS optimization.
Result	std::max_element	Finds the best value in the DP table in O(N).

---

1. The House Robber (Space Optimization)

Input: An array of non-negative integers representing the amount of money stashed in sequential houses.

Condition: Adjacent houses are linked by security systems. Accessing two physically adjacent houses in the sequence triggers an alarm.

Output: The maximum integer amount of money that can be accumulated without triggering the alarm.

Pattern: dp[i] depends only on dp[i-1] and dp[i-2].

Optimization: Do not allocate a vector. Use two integers.

#include <vector>
#include <algorithm>

class Solution {
public:
    int rob(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        if (nums.size() == 1) return nums[0];

        // We only need the previous two states
        int prev2 = 0; // Represents dp[i-2]
        int prev1 = 0; // Represents dp[i-1]

        for (int num : nums) {
            // Recurrence: max(skip current, rob current + previous_2)
            int current = std::max(prev1, prev2 + num);
            
            // Shift window
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
};

---

2. Coin Change (1D DP with Initialization)

Input: An array of integers representing distinct coin denominations and an integer representing a target total amount.

Condition: There is an infinite supply of each coin denomination.

Output: The minimum integer number of coins required to exactly sum to the target amount. If no combination of coins can form the amount, return -1.

Pattern: Unbounded Knapsack.

State: dp[i] = min coins to make amount i.

Initialization: Fill with amount + 1 (a safe "infinity" value).

#include <vector>
#include <algorithm>

int coinChange(std::vector<int>& coins, int amount) {
    // 1. Initialize DP table with a value larger than any possible solution
    // size = amount + 1, default value = amount + 1
    std::vector<int> dp(amount + 1, amount + 1);
    
    // Base Case
    dp[0] = 0;

    // 2. Build Table
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (coin <= i) {
                // Transition
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 3. Check result
    return (dp[amount] > amount) ? -1 : dp[amount];
}

---

3. Longest Increasing Subsequence (The STL Trick)

Problem: Find length of strictly increasing subsequence.

Input: An unsorted array of integers.

Condition: A subsequence is derived by deleting zero or more elements without changing the relative sequential order of the remaining elements. The resulting sequence must be strictly increasing ().

Output: The integer length of the longest valid increasing subsequence.

Standard DP: O(N^2) time.

Patience Sorting (STL): O(N \log N) time using std::lower_bound.

Deep Dive: We maintain a vector tails. tails[i] stores the smallest tail of all increasing subsequences of length i+1. For each number x:

1. If x is larger than all tails, extend the longest subsequence.
2. If x is smaller, it can replace an existing tail to make that subsequence "better" (ending with a smaller number, allowing more future growth).

#include <vector>
#include <algorithm> // for std::lower_bound

int lengthOfLIS(std::vector<int>& nums) {
    if (nums.empty()) return 0;

    std::vector<int> tails;
    
    for (int num : nums) {
        // std::lower_bound returns iterator to first element >= num
        auto it = std::lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            // num is greater than everything in tails
            tails.push_back(num);
        } else {
            // num is a better (smaller) candidate for a subsequence of this length
            *it = num; 
        }
    }
    
    return tails.size();
}

---

4. Unique Paths (2D DP & Memory Layout)

Input: Two integers and representing the rows and columns of a 2D grid.

Condition: An entity begins at the top-left corner (0, 0) and must reach the bottom-right corner (m-1, n-1). Movement is strictly limited to one cell right or one cell down per step.

Output: The total integer number of distinct valid paths that exist from the start coordinate to the end coordinate.

Pattern: Grid traversal.

Memory: vector<vector<int>> is a vector of pointers to vectors. It is not contiguous in memory.

Optimization: Accessing dp[row][col] can be slow due to cache misses.

• Level 1: Use vector<vector<int>> (Good enough for teaching purposes).
• Level 2: Use vector<int> of size N (Space Optimization).

#include <vector>

int uniquePaths(int m, int n) {
    // We only need the previous row to calculate the current row.
    // Initialize with 1s because the first row is always all 1s.
    std::vector<int> row(n, 1);

    for (int i = 1; i < m; ++i) {     // Iterate rows
        for (int j = 1; j < n; ++j) { // Iterate cols
            // row[j] (current cell) = row[j] (value from above) + row[j-1] (value from left)
            row[j] += row[j - 1];
        }
    }
    
    return row[n - 1];
}

---

5. Longest Common Subsequence (2D DP)

Problem: LCS of text1 and text2.

Input: Two strings, text1 and text2.

Condition: A common subsequence is a sequence of characters appearing in both strings in the exact same relative order. The characters are not required to be contiguous within the original strings.

Output: The integer length of the longest common subsequence.

Standard: dp[m+1][n+1].

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

int longestCommonSubsequence(std::string text1, std::string text2) {
    int m = text1.size();
    int n = text2.size();
    
    // 2D Vector: (m+1) rows, (n+1) cols, initialized to 0
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            // Note: String indices are 0-based, DP is 1-based
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

---

6. Word Break / Top-Down Memoization (The Recursive Pattern)

Sometimes Top-Down is more intuitive. In C++, you must pass the memoization table by reference.

Problem: Word Break (Can string s be segmented into dictionary words?)

Input: A target string s and an array of strings wordDict acting as a dictionary.

Condition: The target string s must be completely segmented into a continuous sequence of valid dictionary words. Dictionary words may be reused infinitely.

Output: Boolean true if the string can be successfully segmented, otherwise false.

#include <vector>
#include <string>
#include <unordered_set>

class Solution {
    std::unordered_set<std::string> dict;
    std::vector<int> memo; // -1: unvisited, 0: false, 1: true

public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        dict = std::unordered_set<std::string>(wordDict.begin(), wordDict.end());
        memo.assign(s.size(), -1); // Init memo
        return canBreak(s, 0);
    }

private:
    bool canBreak(const std::string& s, int start) {
        if (start == s.size()) return true;
        if (memo[start] != -1) return memo[start];

        for (int end = start + 1; end <= s.size(); ++end) {
            // substr is expensive O(L), but necessary here
            if (dict.count(s.substr(start, end - start)) && canBreak(s, end)) {
                return memo[start] = 1; // True
            }
        }

        return memo[start] = 0; // False
    }
};

Summary of DP Implementation Patterns

Pattern	C++ Structure	Memory	Complexity
1D Tabulation	vector<int> dp(n, val)	O(N)	O(N)
Space Opt 1D	int prev, curr	O(1)	O(N)
2D Tabulation	vector<vector<int>> dp	O(N \cdot M)	O(N \cdot M)
Space Opt 2D	vector<int> row(n)	O(N)	O(N \cdot M)
LIS Opt	std::lower_bound	O(N)	O(N \log N)
Top-Down	Recursive dfs(idx, memo&)	O(N) Stack	O(N)