区间动态规划-直线石子合并
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数，求把所有石子合并成一堆的最小花费。
解决这个问题，我们可以使用动态规划（DP）。这个问题是典型的区间DP问题。基本思路是这样的：
- 定义状态：
dp[i][j]表示将第i堆到第j堆石子合并成一堆的最小花费。 - 状态转移方程：
dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum[i][j])，其中i <= k < j，sum[i][j]表示第i堆到第j堆石子的总数。 - 初始化：对于任何
i，dp[i][i] = 0，因为单独一堆石子不需要合并。 - 计算顺序：从小区间到大区间，即先计算长度为2的区间，然后是长度为3的区间，依此类推。
代码实现如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | /**************************************************************** * Description: 直线石子合并 * Author: Alex Li * Date: 2024-02-22 16:56:01 * LastEditTime: 2024-02-22 17:10:56 ****************************************************************/ #include <iostream> #include <vector> #include <climits> // 用于INT_MAX using namespace std; int mergeStones(vector<int>& stones) { int n = stones.size(); // 初始化dp数组 vector<vector<int> > dp(n, vector<int>(n, 0)); vector<int> prefixSum(n + 1, 0); //初始化前缀和数组 for (int i = 0; i < n; ++i) { prefixSum[i + 1] = prefixSum[i] + stones[i]; } // 计算所有可能的区间 for (int len = 2; len <= n; ++len) { // 区间长度从2开始 for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; // 计算区间的右端点 dp[i][j] = INT_MAX; //初始化i-j区间的最小值是INT_MAX for (int k = i; k < j; ++k) { // 更新dp[i][j]为合并成一堆的最小花费 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + prefixSum[j + 1] - prefixSum[i]); } } } // 返回合并整个区间的最小花费 return dp[0][n - 1]; } int main() { vector<int> stones = {1, 2, 3, 4, 5}; // 示例石子数组 cout << "Minimum cost to merge all stones: " << mergeStones(stones) << endl; return 0; } |