content: package question1000_minimum_cost_to_merge_stones;
  
  import java.util.Arrays;
  
  /**
   * 状态定义：
   * dp[i][j][k] 表示将 stones 数组中 [i, j] 范围内的石头合并为 k 堆所需的代价。
   *
   * 初始化条件：
   * dp[i][i][1] = 0。
   *
   * 状态转移方程：
   * dp[i][j][k] = min(dp[i][m][1] + dp[m + 1][j][k - 1]), m ∈ [i, j), k ∈ [2, K]。
   * dp[i][j][1] = dp[i][j][K] + A[i] + ... + A[j]。
   *
   * 时间复杂度是 O(K * (n ^ 3))，其中 n 为数组 stones 的长度。空间复杂度是 O(K * (n ^ 2))。
   *
   * 执行用时：5ms，击败65.52%。消耗内存：39.4MB，击败100.00%。
   */
  public class Solution1 {
      public int mergeStones(int[] stones, int K) {
          int n = stones.length;
          if ((n - 1) % (K - 1) != 0) {
              return -1;
          }
          int[] sum = new int[n + 1]; // sum[i] = stones[0] + ... + stones[i - 1]
          for (int i = 1; i < n + 1; i++) {
              sum[i] = sum[i - 1] + stones[i - 1];
          }
          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 / 2 - 1);
              }
          }
          for (int i = 0; i < n; i++) {
              dp[i][i][1] = 0;
          }
          for (int i = n - 1; i >= 0; i--) {
              for (int j = i + 1; j < n; j++) {
                  for (int k = 2; k <= K; k++) {
                      for (int m = i; m < j; m += K - 1) {
                          // 必须要满足 (m - i) % (K - 1) != 0 才能将 [i, m] 范围内的元素合并为 1 个元素
                          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 / 2 - 1) {
                      dp[i][j][1] = dp[i][j][K] + sum[j + 1] - sum[i];
                  }
              }
          }
          return dp[0][n - 1][1];
      }
  }