1000. 合并石头的最低成本-JZTXT

方法：区间dp

解题思路

状态表示：\(f[i][j]\)
- 集合：表示将 \([i, j]\) 的石堆合并成一堆的所有合并方式；
- 属性：集合中合并的所有代价总的最小值。
状态计算：
- 集合划分：将其分为 \([i, m]\) 和 \([m + 1, j]\)，\(m = i + x(k - 1)\)；
- 计算：若 \([i, j]\) 可以被合并为一堆则 \(f[i][j] = min\{f[i][m] + f[m + 1][j] + s[j + 1] - s[i]\}\)；若不能合并，则 \(f[i][j] = min\{f[i][m] + f[m + 1][j]\}\)。

代码

class Solution {
public:
    int mergeStones(vector<int> &stones, int k) {
        int n = stones.size();
        if ((n - 1) % (k - 1)) // 无法合并成一堆
            return -1;

        int s[n + 1];
        s[0] = 0;
        for (int i = 0; i < n; i++)
            s[i + 1] = s[i] + stones[i]; // 前缀和

        int f[n][n];
        for (int i = n - 1; i >= 0; --i) {
            f[i][i] = 0;
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = INT_MAX;
                for (int m = i; m < j; m += k - 1)
                    f[i][j] = min(f[i][j], f[i][m] + f[m + 1][j]);
                if ((j - i) % (k - 1) == 0) // 可以合并成一堆
                    f[i][j] += s[j + 1] - s[i];
            }
        }
        return f[0][n - 1];
    }
};

复杂度分析

时间复杂度：\(O(\frac {n^3} {k})\)；
空间复杂度：\(O(n^2)\)。