Minimum Cost to Cut a Stick LeetCode solution in Java

1
class Solution {
2
  public int minCost(int n, int[] cuts) {
3

4
    int len = cuts.length;
5

6
    Arrays.sort(cuts);
7

8
    int[] arr = new int[len + 2];
9
    for (int i = 1; i <= len; i++) arr[i] = cuts[i - 1];
10

11
    arr[0] = 0;
12
    arr[len + 1] = n;
13
    int[][] dp = new int[len + 1][len + 1];
14
    for (int i = 0; i <= len; i++) for (int j = 0; j <= len; j++) dp[i][j] = -1;
15
    return cut(arr, 1, len, dp);
16
  }
17

18
  int cut(int[] cuts, int i, int j, int[][] dp) {
19
    if (i > j) return 0;
20

21
    if (dp[i][j] != -1) return dp[i][j];
22

23
    int mini = Integer.MAX_VALUE;
24
    for (int k = i; k <= j; k++) {
25
      int cost = cuts[j + 1] - cuts[i - 1] + cut(cuts, i, k - 1, dp) + cut(cuts, k + 1, j, dp);
26
      mini = Math.min(cost, mini);
27
    }
28

29
    return dp[i][j] = mini;
30
  }
31
}