Minimum Difficulty of a Job Schedule LeetCode solution in JavaScript

1
var minDifficulty = function (jobDifficulty, d) {
2
  // don't have enought jobs to distribute
3
  if (jobDifficulty.length < d) {
4
    return -1;
5
  }
6

7
  // in dynamic programming top-down approach
8
  // we need to have memoisation to not repeat calculations
9
  let memo = new Array(d + 1)
10
    .fill(-1)
11
    .map(() => new Array(jobDifficulty.length + 1).fill(-1));
12

13
  const dp = function (D, N) {
14
    // if we calculated this before, just return
15
    if (-1 != memo[D][N]) {
16
      return memo[D][N];
17
    }
18

19
    // if we have only 1 day, we just need to take all jobs
20
    // and return the highest difficulty
21
    if (1 == D) {
22
      memo[D][N] = 0;
23
      for (let i = 0; i < N; i++) {
24
        if (memo[D][N] < jobDifficulty[i]) {
25
          memo[D][N] = jobDifficulty[i];
26
        }
27
      }
28
      return memo[D][N];
29
    }
30

31
    // otherwise, we use our recurrence relation to calculate
32
    memo[D][N] = 1000 * D;
33

34
    let max_job_per_day = N - D + 1;
35
    let max_difficulty = 0;
36

37
    // iteration for recurrence relation
38
    for (let X = 1; X <= max_job_per_day; X++) {
39
      // count max in the current range
40
      // len - X is the starting point for
41
      // the last day in D days
42
      if (jobDifficulty[N - X] > max_difficulty) {
43
        max_difficulty = jobDifficulty[N - X];
44
      }
45
      // recurrence relation
46
      // we took X jobs,
47
      // so we still have N - X jobs for D - 1 days
48
      let min_sum = max_difficulty + dp(D - 1, N - X);
49

50
      // pick the min only
51
      if (min_sum < memo[D][N]) {
52
        memo[D][N] = min_sum;
53
      }
54
    }
55

56
    return memo[D][N];
57
  };
58

59
  return dp(d, jobDifficulty.length);
60
};