LeetCode 1000. 合并石头的最低成本（经典区间DP）

1000. 合并石头的最低成本

定义dp[i][j]为尽可能多的合并区间[i, j] 所需的成本，不一定能合并成一堆，但合并完成后剩下的堆数一定小于k，更具体地，剩余的堆数一定是(n - 1) % (k - 1) + 1。

将区间[i，j]划分为两部分。 我们保证将左部分合并成1堆，而尽可能多地合并右部分。（左部分需要满足(len - 1) % (k - 1) == 0）。 右部分剩余堆数满足1 <= remain <= k - 1，如果最后右部分剩余k-1堆（也即(j - i) % (k - 1) == 0），则还可以继续将这两部分合并成1堆。 因此合并区间[i，j]的成本是合并其左右部分成本之和（对于最优的划分）。如果可以进一步合并的话，则额外的成本是sum(i, j)。 状态转移方程为：dp[i][j] = min(dp[i][p] + dp[p + 1][j]), i <= p < j，如果可以继续合并，dp[i][j] += sum(i, j)。

为什么划分的方式是左部分合并成1堆，右部分合并成k-1堆？左部分k-1，右部分1；左部分2，右部分k-2…这些方式可行吗？ 可行的划分方式只能是1和k-1，左右当然不重要。

这样的话枚举的区间长度就必须从k开始了，因为长度在[1，k-1]之间的区间已经无法进行合并了，它们的dp[i][j] == 0。

参考链接

class Solution {public:int mergeStones(vector<int>& stones, int K) {int n = stones.size();if ((n - 1) % (K - 1) != 0) return -1;vector<int> prefix(n + 1);for (int i = 1; i <= n; ++i) {prefix[i] = prefix[i - 1] + stones[i - 1];}// 令 f[i][j] 表示为 [i,j] 空间内"尽可能多合并"的最小成本// 所谓尽可能多地合并的意思是，f[i][j]合并成的堆数==(len - 1) % (k - 1) + 1vector<vector<int>> f(n, vector<int>(n));for (int len = K; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1; // 枚举区间 [i, j]f[i][j] = INT_MAX;for (int m = i; m < j; m += K - 1) {// 枚举断点 m（这里的步长必须是K-1，以保证左边部分可以合并成1堆）f[i][j] = min(f[i][j], f[i][m] + f[m + 1][j]);}if ((len - 1) % (K - 1) == 0) {f[i][j] += prefix[j + 1] - prefix[i];}}}return f[0][n - 1];}};