LeetCode 1000. Minimum Cost to Merge Stones

题目链接：https://leetcode.com/problems/minimum-cost-to-merge-stones/

题意：有$N$堆石头排成一行，第$i$堆石头有$stones[i]$个石头，现在需要将所有堆的石头合并成一堆，以堆为单位进行操作，每次只能将$K$个连续的堆合并成一堆，每次合并的代价为这$K$堆石头的石头数之和，问合成一堆的最小代价是多少，若不能合并成一堆，则返回-1。石头的堆数不超过30，$K$的值不超过30，每堆石头的数目不超过100。

思路：首先确定能合成一堆的条件，即$N=K,2*K-1,3*K-2...$，因此$N$满足的条件为$(N-1)%K=0$，区间dp的思路，$dp[i][j]表示从$i$堆石头到第$j$堆石头需要的代价。枚举$k$，dp方程为$dp[i][j]=dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])$，当$(j-i)%K==0$时，即恰好可以合并成一堆时，需要加一次代价值，即$dp[i][j]+=sum[j]-sum[i-1]$，枚举k时，由于石子堆数-1必须为$K-1$的倍数，因此k可每隔K-1个枚举一次。

class Solution {
public:
    int mergeStones(vector& stones, int K) {
        int cnt=stones.size(); 
        while(cnt>=K) //能否合并成一堆
            cnt = cnt/K+cnt%K;
        if(cnt!=1)
            return -1;
        int **dp = new int *[stones.size()];
        for(int i=0;i=0;i--)
            for(int j=i;j