# 1000. Minimum Cost to Merge Stones
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-cost-to-merge-stones/description/
## 思路
这道题的最后一步是把k个element合并成1个，也就是说我们要把stones分成k个区间 所以我们会想到用**区间型I**(把s分成k个序列 求一个最优性质)
但事实上没有这么简单 因为这里面涉及一系列子问题 也就是如果s[i:j]可以被分成k个区间 我们可以拿着它和其他stones merge起来 所以这是一道**区间型II**的问题
所以我们令```dp[i][j][k]```是将```stones[i:j]```合并成```k```个区间的最小cost

基层循环架构：

for (int len = 2; len<=N; len++)
  for (int i=0; i<=N-len; i++)
  {
    int j = i+len-1;    // 这两层循环，我们遍历i,j
    for (int k=2; k<=K; k++)  // 这一层循环我们遍历k
    {
      for (int m=i; m<j; m++) // 这一层循环我们遍历拆分点m，使得分成第一个区间和剩下k-1个区间
      {
        dp[i][j][k] = min(dp[i][m][1]+dp[m+1][j][k-1]) ;
      }
    }
    dp[i][j][1] = dp[i][j][K]+sum[i~j];
  }
return dp[0][N-1][1];

## Code

class Solution {
    public int mergeStones(int[] stones, int K) {
        int n = stones.length;
        int[][][] dp = new int[n][n][K+1];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                Arrays.fill(dp[i][j], Integer.MAX_VALUE);
            }
        }
        int[] prefix = new int[n];
        int sum = 0;
        for(int i=0; i<n; i++){
            sum += stones[i];
            prefix[i] = sum;
        }
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(i==j) dp[i][i][1] = 0;
            }
        }
        for(int len=2; len<=n; len++){
            for(int i=0; i+len-1<n; i++){
                int j=i+len-1;
                for(int k=2; k<=Math.min(K,len); k++){
                    for(int m=i; j-(m+1)+1>=k-1; m++){
                        if (dp[i][m][1]==Integer.MAX_VALUE || dp[m+1][j][k-1]==Integer.MAX_VALUE) continue;
                        dp[i][j][k] = Math.min(dp[i][j][k], dp[i][m][1]+dp[m+1][j][k-1]);
                    }
                }
                if(dp[i][j][K]!=Integer.MAX_VALUE) dp[i][j][1] = dp[i][j][K]+prefix[j]-(i==0?0:prefix[i-1]);
            }
        }
        if(dp[0][n-1][1]==Integer.MAX_VALUE) return -1;
        return dp[0][n-1][1];
    }
}