Minimum Cost to Merge Stones LeetCode solution in Java

1
class Solution {
2
  int prefix[];
3

4
  public int mergeStones(int[] stones, int k) {
5
    int n = stones.length;
6
    if ((n - 1) % (k - 1) != 0) return -1;
7
    prefix = new int[stones.length + 1];
8
    prefix[0] = 0;
9
    int sum = 0;
10
    for (int i = 0; i < stones.length; i++) {
11
      sum += stones[i];
12
      prefix[i + 1] = sum;
13
    }
14
    int dp[][] = new int[stones.length][stones.length];
15
    for (int i = 0; i < dp.length; i++) {
16
      for (int j = 0; j < dp[0].length; j++) {
17
        dp[i][j] = -1;
18
      }
19
    }
20
    return check(prefix, k, 0, stones.length - 1, dp);
21
  }
22

23
  public int check(int[] prefix, int k, int i, int j, int dp[][]) {
24
    if (i >= j) {
25
      return 0;
26
    }
27
    if (dp[i][j] != -1) {
28
      return dp[i][j];
29
    }
30
    int min = Integer.MAX_VALUE;
31
    for (int t = i; t < j; t = t + k - 1) {
32
      int min1 = check(prefix, k, i, t, dp) + check(prefix, k, t + 1, j, dp);
33
      min = Math.min(min, min1);
34
    }
35
    if ((j - i) % (k - 1) == 0) {
36
      min += prefix[j + 1] - prefix[i];
37
    }
38
    dp[i][j] = min;
39
    return min;
40
  }
41
}
42

43
class Solution0 {
44
  public int mergeStones(int[] stones, int K) {
45
    int n = stones.length;
46
    if ((n - 1) % (K - 1) > 0) return -1;
47

48
    int[] prefix = new int[n + 1];
49
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
50

51
    int[][] dp = new int[n][n];
52
    for (int m = K; m <= n; ++m)
53
      for (int i = 0; i + m <= n; ++i) {
54
        int j = i + m - 1;
55
        dp[i][j] = Integer.MAX_VALUE;
56
        for (int mid = i; mid < j; mid += K - 1)
57
          dp[i][j] = Math.min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
58
        if ((j - i) % (K - 1) == 0) dp[i][j] += prefix[j + 1] - prefix[i];
59
      }
60
    return dp[0][n - 1];
61
  }
62
}