Solution including Memoization:
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
Map<Map.Entry<Integer, Integer>, Integer> memo = new HashMap<>();
if (n < d || n > 300)
return -1;
if (n == d) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += jobDifficulty[i];
}
return sum;
}
return dfs(jobDifficulty, 0, d, memo);
}
private int dfs(int[] jobDifficulty, int start, int d, Map<Map.Entry<Integer, Integer>, Integer> memo) {
if (d == 1) {
int max = 0;
for (int i = start; i < jobDifficulty.length; i++) {
max = Math.max(max, jobDifficulty[i]);
}
return max;
}
Map.Entry<Integer, Integer> key = Map.entry(d, start);
if(memo.containsKey(key)) {
return memo.get(key);
}
int maxDifficulty = 0;
int minDifficultyOfSchedule = Integer.MAX_VALUE;
for (int i = start; i < jobDifficulty.length - (d - 1); i++) {
maxDifficulty = Math.max(maxDifficulty, jobDifficulty[i]);
minDifficultyOfSchedule = Math.min(minDifficultyOfSchedule,
maxDifficulty + dfs(jobDifficulty, i + 1, d - 1, memo));
}
memo.put(key, minDifficultyOfSchedule);
return minDifficultyOfSchedule;
}
@mod I am getting lot of 404’s when clicking some of the links. For e.g. Clicking Next on this page resulting on 404. Can you fix it please ?