Advanced Dynamic Programming

Master interval DP, tree DP, and complex optimization techniques

Overview

Advanced dynamic programming is the core technique for solving complex optimization problems. This chapter explores interval DP, tree DP, advanced knapsack variations, and various DP optimization techniques, providing powerful tools for challenging problems in world-class competitions.

Core Content

1. Interval Dynamic Programming

Interval DP is a classic technique for interval-related problems, solving optimal substructure problems by enumerating split points. 

// Classic interval DP problems
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Problem 1: Matrix Chain Multiplication
int matrixChainMultiplication(vector<int>& dimensions) {
    int n = dimensions.size() - 1; // n matrices
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // len is the chain length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            
            // Try all possible split points
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + 
                          dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[0][n - 1];
}

// Problem 2: Palindrome Partitioning (minimum cuts)
int minPalindromePartitions(string s) {
    int n = s.length();
    
    // Preprocessing: check if substring is palindrome
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
    
    // Odd length palindromes
    for (int center = 0; center < n; center++) {
        int left = center, right = center;
        while (left >= 0 && right < n && s[left] == s[right]) {
            isPalindrome[left][right] = true;
            left--;
            right++;
        }
    }
    
    // Even length palindromes
    for (int center = 0; center < n - 1; center++) {
        int left = center, right = center + 1;
        while (left >= 0 && right < n && s[left] == s[right]) {
            isPalindrome[left][right] = true;
            left--;
            right++;
        }
    }
    
    // DP: calculate minimum cuts
    vector<int> dp(n, INT_MAX);
    
    for (int i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            dp[i] = 0; // Entire prefix is palindrome
        } else {
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    
    return dp[n - 1];
}

// Problem 3: Optimal Binary Search Tree
double optimalBST(vector<double>& keys, vector<double>& freq) {
    int n = keys.size();
    vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
    vector<double> sum(n + 1, 0);
    
    // Calculate frequency prefix sum
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + freq[i - 1];
    }
    
    // Interval DP
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = DBL_MAX;
            double freqSum = sum[j] - sum[i - 1];
            
            // Try each node as root
            for (int root = i; root <= j; root++) {
                double cost = freqSum;
                if (root > i) cost += dp[i][root - 1];
                if (root < j) cost += dp[root + 1][j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    
    return dp[1][n];
}

int main() {
    // Test matrix chain multiplication
    vector<int> dimensions = {40, 20, 30, 10, 30}; // Dimensions of 4 matrices
    cout << "Matrix chain minimum scalar multiplications: " 
         << matrixChainMultiplication(dimensions) << endl;
    
    // Test palindrome partitioning
    string s = "aabcbaa";
    cout << "String "" << s << "" minimum partitions: " 
         << minPalindromePartitions(s) << endl;
    
    // Test optimal BST
    vector<double> keys = {10, 12, 20};
    vector<double> freq = {34, 8, 50};
    cout << "Optimal BST expected search cost: " 
         << optimalBST(keys, freq) << endl;
    
    return 0;
}

2. Tree Dynamic Programming

Tree DP performs dynamic programming on tree structures, solving optimization problems on trees through DFS traversal and state transitions. 

// Classic tree DP problems
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

// Problem 1: Tree Diameter
class TreeDiameter {
private:
    int maxDiameter;
    
    int dfs(TreeNode* root) {
        if (!root) return 0;
        
        vector<int> depths;
        for (TreeNode* child : root->children) {
            depths.push_back(dfs(child));
        }
        
        // Find two deepest paths
        sort(depths.rbegin(), depths.rend());
        
        int diameter = 0;
        if (depths.size() >= 2) {
            diameter = depths[0] + depths[1];
        } else if (depths.size() == 1) {
            diameter = depths[0];
        }
        
        maxDiameter = max(maxDiameter, diameter);
        
        return depths.empty() ? 1 : depths[0] + 1;
    }
    
public:
    int findDiameter(TreeNode* root) {
        maxDiameter = 0;
        dfs(root);
        return maxDiameter;
    }
};

// Problem 2: Maximum Independent Set on Tree
class MaxIndependentSet {
private:
    pair<int, int> dfs(TreeNode* root) {
        if (!root) return {0, 0};
        
        int include = root->val; // Include current node
        int exclude = 0;         // Exclude current node
        
        for (TreeNode* child : root->children) {
            auto childResult = dfs(child);
            include += childResult.second; // Child must not be selected
            exclude += max(childResult.first, childResult.second); // Child can be selected or not
        }
        
        return {include, exclude};
    }
    
public:
    int maxIndependentSet(TreeNode* root) {
        auto result = dfs(root);
        return max(result.first, result.second);
    }
};

// Problem 3: Tree Centroid
class TreeCentroid {
private:
    int n;
    vector<vector<int>> adj;
    vector<int> subtreeSize;
    int centroid;
    int minMaxSubtree;
    
    void dfs(int u, int parent) {
        subtreeSize[u] = 1;
        int maxSubtree = 0;
        
        for (int v : adj[u]) {
            if (v != parent) {
                dfs(v, u);
                subtreeSize[u] += subtreeSize[v];
                maxSubtree = max(maxSubtree, subtreeSize[v]);
            }
        }
        
        // Consider subtree in parent direction
        maxSubtree = max(maxSubtree, n - subtreeSize[u]);
        
        if (maxSubtree < minMaxSubtree) {
            minMaxSubtree = maxSubtree;
            centroid = u;
        }
    }
    
public:
    int findCentroid(vector<vector<int>>& edges) {
        n = edges.size() + 1;
        adj.resize(n);
        subtreeSize.resize(n);
        minMaxSubtree = n;
        
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        dfs(0, -1);
        return centroid;
    }
};

// Problem 4: Tree Knapsack
class TreeKnapsack {
private:
    vector<vector<int>> adj;
    vector<int> weight, value;
    vector<vector<int>> dp;
    
    void dfs(int u, int parent, int capacity) {
        // Initialize: consider only current node
        for (int w = 0; w <= capacity; w++) {
            if (w >= weight[u]) {
                dp[u][w] = value[u];
            }
        }
        
        // Process each subtree
        for (int v : adj[u]) {
            if (v != parent) {
                dfs(v, u, capacity);
                
                // Merge subtree results
                for (int w = capacity; w >= 0; w--) {
                    for (int k = 0; k <= w; k++) {
                        dp[u][w] = max(dp[u][w], dp[u][k] + dp[v][w - k]);
                    }
                }
            }
        }
    }
    
public:
    int solve(vector<vector<int>>& edges, vector<int>& weights, vector<int>& values, int capacity) {
        int n = weights.size();
        adj.resize(n);
        weight = weights;
        value = values;
        dp.assign(n, vector<int>(capacity + 1, 0));
        
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        dfs(0, -1, capacity);
        return dp[0][capacity];
    }
};

int main() {
    // Build test tree
    TreeNode* root = new TreeNode(1);
    root->children.push_back(new TreeNode(2));
    root->children.push_back(new TreeNode(3));
    root->children[0]->children.push_back(new TreeNode(4));
    root->children[0]->children.push_back(new TreeNode(5));
    root->children[1]->children.push_back(new TreeNode(6));
    
    // Test tree diameter
    TreeDiameter diameterSolver;
    cout << "Tree diameter: " << diameterSolver.findDiameter(root) << endl;
    
    // Test maximum independent set
    MaxIndependentSet misSolver;
    cout << "Maximum independent set size: " << misSolver.maxIndependentSet(root) << endl;
    
    // Test tree centroid
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
    TreeCentroid centroidSolver;
    cout << "Tree centroid: " << centroidSolver.findCentroid(edges) << endl;
    
    // Test tree knapsack
    vector<int> weights = {2, 1, 3, 2, 1, 4};
    vector<int> values = {3, 2, 4, 4, 2, 5};
    TreeKnapsack knapsackSolver;
    cout << "Tree knapsack maximum value: " 
         << knapsackSolver.solve(edges, weights, values, 7) << endl;
    
    return 0;
}

3. Advanced Knapsack Problems

// Advanced knapsack problem variations
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Multiple knapsack (binary optimization)
int multipleKnapsack(vector<int>& weights, vector<int>& values, vector<int>& counts, int capacity) {
    vector<int> w, v;
    
    // Binary decomposition
    for (int i = 0; i < weights.size(); i++) {
        int count = counts[i];
        for (int k = 1; k <= count; k *= 2) {
            w.push_back(k * weights[i]);
            v.push_back(k * values[i]);
            count -= k;
        }
        if (count > 0) {
            w.push_back(count * weights[i]);
            v.push_back(count * values[i]);
        }
    }
    
    // 0-1 knapsack
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < w.size(); i++) {
        for (int j = capacity; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    
    return dp[capacity];
}

// Group knapsack
int groupKnapsack(vector<vector<pair<int, int>>>& groups, int capacity) {
    vector<int> dp(capacity + 1, 0);
    
    for (auto& group : groups) {
        for (int j = capacity; j >= 0; j--) {
            // Try selecting each item in the group
            for (auto& item : group) {
                int weight = item.first, value = item.second;
                if (j >= weight) {
                    dp[j] = max(dp[j], dp[j - weight] + value);
                }
            }
        }
    }
    
    return dp[capacity];
}

// Dependent knapsack (tree knapsack)
class DependentKnapsack {
private:
    struct Item {
        int weight, value;
        vector<int> children;
    };
    
    vector<Item> items;
    vector<vector<int>> dp;
    
    void dfs(int u, int capacity) {
        // Initialize: select current item
        for (int w = items[u].weight; w <= capacity; w++) {
            dp[u][w] = items[u].value;
        }
        
        // Process dependent sub-items
        for (int child : items[u].children) {
            dfs(child, capacity);
            
            // Merge sub-item results
            for (int w = capacity; w >= items[u].weight; w--) {
                for (int k = 0; k <= w - items[u].weight; k++) {
                    dp[u][w] = max(dp[u][w], dp[u][w - k] + dp[child][k]);
                }
            }
        }
    }
    
public:
    int solve(vector<pair<int, int>>& itemData, vector<vector<int>>& dependencies, int capacity) {
        int n = itemData.size();
        items.resize(n);
        dp.assign(n, vector<int>(capacity + 1, 0));
        
        for (int i = 0; i < n; i++) {
            items[i].weight = itemData[i].first;
            items[i].value = itemData[i].second;
            items[i].children = dependencies[i];
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) {
            // Check if root item (not depended by others)
            bool isRoot = true;
            for (int j = 0; j < n; j++) {
                for (int child : items[j].children) {
                    if (child == i) {
                        isRoot = false;
                        break;
                    }
                }
                if (!isRoot) break;
            }
            
            if (isRoot) {
                dfs(i, capacity);
                for (int w = 0; w <= capacity; w++) {
                    result = max(result, dp[i][w]);
                }
            }
        }
        
        return result;
    }
};

// 2D knapsack
int twoDimensionalKnapsack(vector<int>& weights, vector<int>& volumes, vector<int>& values, 
                          int maxWeight, int maxVolume) {
    vector<vector<int>> dp(maxWeight + 1, vector<int>(maxVolume + 1, 0));
    
    for (int i = 0; i < weights.size(); i++) {
        for (int w = maxWeight; w >= weights[i]; w--) {
            for (int v = maxVolume; v >= volumes[i]; v--) {
                dp[w][v] = max(dp[w][v], dp[w - weights[i]][v - volumes[i]] + values[i]);
            }
        }
    }
    
    return dp[maxWeight][maxVolume];
}

int main() {
    // Test multiple knapsack
    vector<int> weights = {2, 3, 4};
    vector<int> values = {3, 4, 5};
    vector<int> counts = {3, 2, 1};
    cout << "Multiple knapsack maximum value: " 
         << multipleKnapsack(weights, values, counts, 10) << endl;
    
    // Test group knapsack
    vector<vector<pair<int, int>>> groups = {
        {{1, 2}, {2, 3}, {3, 4}},  // Group 1
        {{2, 3}, {3, 5}, {4, 6}},  // Group 2
        {{1, 1}, {4, 7}}           // Group 3
    };
    cout << "Group knapsack maximum value: " 
         << groupKnapsack(groups, 8) << endl;
    
    // Test 2D knapsack
    vector<int> weights2d = {2, 3, 4};
    vector<int> volumes2d = {1, 3, 2};
    vector<int> values2d = {3, 5, 4};
    cout << "2D knapsack maximum value: " 
         << twoDimensionalKnapsack(weights2d, volumes2d, values2d, 6, 4) << endl;
    
    return 0;
}

Problem-Solving Tips

šŸŽÆ State Design

Proper DP state design is crucial. Consider interval endpoints for interval DP, subtree information for tree DP, and multi-dimensional states for complex problems.

āš” Optimization Techniques

Use rolling arrays for space optimization, binary decomposition for multiple knapsack, memoization for complex state transitions.

šŸ”„ Transition Equations

Carefully analyze state transition equations, pay attention to boundary conditions and special cases. Consider parent-child relationships in tree DP, enumerate split points in interval DP.

šŸ§® Complexity Analysis

Accurately analyze time and space complexity. Interval DP is typically O(nĀ³), tree DP is O(n), knapsack problems consider capacity constraints.

šŸ“š Chapter Index