1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
private Integer[][] memo;
public int minDifficulty(int[] jobDifficulty, int d) {
memo = new Integer[jobDifficulty.length][d + 1];
int ans = backtrack(jobDifficulty, 0, d);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private int backtrack(int[] diffi, int pos, int remain) {
if (diffi.length - pos < remain) {
return Integer.MAX_VALUE;
}
if (pos == diffi.length && remain == 0) {
return 0;
} else if (remain == 0) {
return Integer.MAX_VALUE;
}
if (memo[pos][remain] != null) {
return memo[pos][remain];
}
int ans = Integer.MAX_VALUE, currDifficulty = -1;
for (int i = pos; i < diffi.length; i++) {
currDifficulty = Math.max(currDifficulty, diffi[i]);
int scheduleBehind = backtrack(diffi, i + 1, remain - 1);
if (scheduleBehind != Integer.MAX_VALUE) {
ans = Math.min(ans, currDifficulty + scheduleBehind);
}
}
return memo[pos][remain] = ans;
}
}
|
