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];}};