// 区间动态规划经典问题
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 问题1：矩阵链乘法
int matrixChainMultiplication(vector<int>& dimensions) {
    int n = dimensions.size() - 1; // n个矩阵
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    // len是链的长度
    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;
            
            // 尝试所有可能的分割点
            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];
}

// 问题2：回文串分割（最少分割次数）
int minPalindromePartitions(string s) {
    int n = s.length();
    
    // 预处理：判断子串是否为回文
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
    
    // 奇数长度回文
    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++;
        }
    }
    
    // 偶数长度回文
    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：计算最少分割次数
    vector<int> dp(n, INT_MAX);
    
    for (int i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            dp[i] = 0; // 整个前缀是回文
        } 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];
}

// 问题3：最优二叉搜索树
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);
    
    // 计算频率前缀和
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + freq[i - 1];
    }
    
    // 区间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];
            
            // 尝试每个节点作为根
            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() {
    // 测试矩阵链乘法
    vector<int> dimensions = {40, 20, 30, 10, 30}; // 4个矩阵的维度
    cout << "矩阵链乘法最少标量乘法次数： " 
         << matrixChainMultiplication(dimensions) << endl;
    
    // 测试回文分割
    string s = "aabcbaa";
    cout << "字符串 "" << s << "" 的最少分割次数： " 
         << minPalindromePartitions(s) << endl;
    
    // 测试最优BST
    vector<double> keys = {10, 12, 20};
    vector<double> freq = {34, 8, 50};
    cout << "最优BST的期望搜索成本： " 
         << optimalBST(keys, freq) << endl;
    
    return 0;
}

// 树形动态规划经典问题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

// 问题1：树的直径
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));
        }
        
        // 找到最深的两条路径
        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;
    }
};

// 问题2：树上最大独立集
class MaxIndependentSet {
private:
    pair<int, int> dfs(TreeNode* root) {
        if (!root) return {0, 0};
        
        int include = root->val; // 包含当前节点
        int exclude = 0;         // 不包含当前节点
        
        for (TreeNode* child : root->children) {
            auto childResult = dfs(child);
            include += childResult.second; // 子节点必须不选
            exclude += max(childResult.first, childResult.second); // 子节点可选可不选
        }
        
        return {include, exclude};
    }
    
public:
    int maxIndependentSet(TreeNode* root) {
        auto result = dfs(root);
        return max(result.first, result.second);
    }
};

// 问题3：树的重心
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]);
            }
        }
        
        // 考虑父节点方向的子树
        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;
    }
};

// 问题4：树上背包
class TreeKnapsack {
private:
    vector<vector<int>> adj;
    vector<int> weight, value;
    vector<vector<int>> dp;
    
    void dfs(int u, int parent, int capacity) {
        // 初始化：只考虑当前节点
        for (int w = 0; w <= capacity; w++) {
            if (w >= weight[u]) {
                dp[u][w] = value[u];
            }
        }
        
        // 处理每个子树
        for (int v : adj[u]) {
            if (v != parent) {
                dfs(v, u, capacity);
                
                // 合并子树的结果
                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() {
    // 构建测试树
    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));
    
    // 测试树的直径
    TreeDiameter diameterSolver;
    cout << "树的直径： " << diameterSolver.findDiameter(root) << endl;
    
    // 测试最大独立集
    MaxIndependentSet misSolver;
    cout << "最大独立集大小： " << misSolver.maxIndependentSet(root) << endl;
    
    // 测试树的重心
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}};
    TreeCentroid centroidSolver;
    cout << "树的重心： " << centroidSolver.findCentroid(edges) << endl;
    
    // 测试树上背包
    vector<int> weights = {2, 1, 3, 2, 1, 4};
    vector<int> values = {3, 2, 4, 4, 2, 5};
    TreeKnapsack knapsackSolver;
    cout << "树上背包最大价值： " 
         << knapsackSolver.solve(edges, weights, values, 7) << endl;
    
    return 0;
}

// 高级背包问题变种
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 多重背包（二进制优化）
int multipleKnapsack(vector<int>& weights, vector<int>& values, vector<int>& counts, int capacity) {
    vector<int> w, v;
    
    // 二进制拆分
    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]);
        }
    }
    
    // 01背包
    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];
}

// 分组背包
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--) {
            // 尝试选择组内每个物品
            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];
}

// 有依赖的背包（树形背包）
class DependentKnapsack {
private:
    struct Item {
        int weight, value;
        vector<int> children;
    };
    
    vector<Item> items;
    vector<vector<int>> dp;
    
    void dfs(int u, int capacity) {
        // 初始化：选择当前物品
        for (int w = items[u].weight; w <= capacity; w++) {
            dp[u][w] = items[u].value;
        }
        
        // 处理依赖的子物品
        for (int child : items[u].children) {
            dfs(child, capacity);
            
            // 合并子物品的结果
            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++) {
            // 检查是否为根物品（没有被其他物品依赖）
            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;
    }
};

// 二维背包
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() {
    // 测试多重背包
    vector<int> weights = {2, 3, 4};
    vector<int> values = {3, 4, 5};
    vector<int> counts = {3, 2, 1};
    cout << "多重背包最大价值： " 
         << multipleKnapsack(weights, values, counts, 10) << endl;
    
    // 测试分组背包
    vector<vector<pair<int, int>>> groups = {
        {{1, 2}, {2, 3}, {3, 4}},  // 第一组
        {{2, 3}, {3, 5}, {4, 6}},  // 第二组
        {{1, 1}, {4, 7}}           // 第三组
    };
    cout << "分组背包最大价值： " 
         << groupKnapsack(groups, 8) << endl;
    
    // 测试二维背包
    vector<int> weights2d = {2, 3, 4};
    vector<int> volumes2d = {1, 3, 2};
    vector<int> values2d = {3, 5, 4};
    cout << "二维背包最大价值： " 
         << twoDimensionalKnapsack(weights2d, volumes2d, values2d, 6, 4) << endl;
    
    return 0;
}