Minimum Difficulty of a Job Schedule LeetCode solution in Java

1
class Solution {
2
  // Given an array, cut it into d contiguous subarray and return the minimum sum of max of each
3
  // subarray.
4
  public int minDifficulty(int[] jobDifficulty, int d) {
5
    if (d > jobDifficulty.length) {
6
      return -1;
7
    }
8

9
    int[][] memo = new int[d + 1][jobDifficulty.length];
10
    for (int[] m : memo) {
11
      Arrays.fill(m, -1);
12
    }
13

14
    return getMinDays(jobDifficulty, d, memo, 0);
15
  }
16

17
  private int getMinDays(int[] jobDifficulty, int d, int[][] memo, int idx) {
18
    if (d == 1) {
19
      int max = 0;
20
      while (idx < jobDifficulty.length) {
21
        max = Math.max(max, jobDifficulty[idx]);
22
        idx++;
23
      }
24
      return max;
25
    }
26

27
    if (memo[d][idx] != -1) return memo[d][idx];
28

29
    int max = 0;
30
    int res = Integer.MAX_VALUE;
31
    // [6,5,4,3,2,1], d=5 => we don't want the cut at 4th position in the array because we won't be
32
    // able to divide it into 5 parts
33
    for (int i = idx; i < jobDifficulty.length - d + 1; i++) {
34
      max = Math.max(max, jobDifficulty[i]);
35
      res = Math.min(res, max + getMinDays(jobDifficulty, d - 1, memo, i + 1));
36
    }
37

38
    memo[d][idx] = res;
39
    return memo[d][idx];
40
  }
41
}