传送门

设 f[l][r][k] 为 l， r， 里分成 k 段的代价。

• 以长度为阶段。
• f[l][r][k] = min(f[l][r][k], f[l][mid][k – 1] + f[mid + 1][r][1])
• 答案就是f[l][r][1]

每个k只用从k-1和1转移，因为对于任何k-n,n，一定可以分解为k-1,1,1,1,..1;所以对于前面的状态都是被考虑过的，不用再重复考虑。

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int f[63][63][63], sum[33];
    int mergeStones(vector<int>& stones, int K) {
        memset(f, 0x3f, sizeof f);
        memset(sum, 0, sizeof sum);
        int s = stones.size();
        for(int i = 1; i <= s; i++) sum[i] = sum[i - 1] + stones[i - 1];
        while(s >= K)
        {
            s -= K;
            s++;
        }
        if(s > 1) return -1;
        s = stones.size();
        for(int i = 1; i <= s; i++) f[i][i][1] = 0;
        for(int len = 2; len <= s; len++)
        {
            for(int l = 1; l <= s - len + 1; l++)
            {
                int r = l + len - 1;
                for(int k = 2; k <= K; k++)
                {    
                    for(int j = l; j < r; j++)
                    {
                        f[l][r][k]=min(f[l][r][k],f[l][j][k-1]+f[j+1][r][1]);
                    }
                }
                f[l][r][1] = min(f[l][r][1], f[l][r][K] + sum[r] - sum[l - 1]);
            }
        }
        return f[1][s][1];
    }
};