# Minimum difficulty of a job schedule

May 16, 2023 · 858 words · 5 min

Today I’ll share an article about `Dynamic Programing` .

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

wikipedia - Dynamic programming

## Question

You want to schedule a list of jobs in `d` days. Jobs are dependent (i.e To work on the `ith` job, you have to finish all the jobs `j` where `0 <= j < i`).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the `d` days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array `jobDifficulty` and an integer `d`. The difficulty of the `ith` job is `jobDifficulty[i]`.

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return `-1`.

Example 1: ``````Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
``````

Example 2:

``````Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
``````

Example 3:

``````Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.
``````

Constraints:

• `1 <= jobDifficulty.length <= 300`
• `0 <= jobDifficulty[i] <= 1000`
• `1 <= d <= 10`

## Solution

### Thinking

We need to split \$jobDifficulty\$ to \$d\$ parts, and make the sum of the maximum of each parts be lowest.

If the \$d\$ equal `1`, the answer is simple: \$ \max_{i=0}^n jobDifficulty_i \$, so what if \$d\$ is greater than \$1\$?

We can split at index \$k\$ , so we get \$2\$ parts, the first part \$jobDifficulty[0,k]\$ and the second part \$jobDifficulty[k+1, n]\$,

so we can calculate the maximum of the first part and the second part, and then we succeeded in reducing the scale of the problem, we can keep splitting the first part, for different \$k\$, we’ll get different parts and different maximum of each part.

Let’s start Dynamic programming. In this article, I’ll use Recursion to implement Dynamic programming.

DP Definition

We can declare a function as below, this function will return the minimal sum of \$count\$ parts from \$nums[0, index]\$.

``````int dp(int[] nums, int index, int count)
``````

Base case

• If the \$length\$ of \$nums[0, index]\$ is less than \$count\$, it’s impossible to split.
• If the \$count=1\$ , just return \$\max_{i=0}^n nums_i\$

State transition equation

If the \$count>1\$, we will declare a split point \$i\$ iterates from \$0…index-1\$, so we get a answer and a sub problem, to solve the sub problem, we can call `dp` function again. So we can get a State transition equation. \$\$ dp[index][count] = min(dp[index][count], current+subProblem) \$\$

### Code

``````class Solution {
private int[][] memo;

// Human translate
// split the `jobDifficulty` array to `d` parts, make the sum of the maximum of each parts be lowest
public int minDifficulty(int[] jobDifficulty, int d) {
if (jobDifficulty.length < d) {
return -1;
}
memo = new int[jobDifficulty.length][d+1];
for(var i = 0; i < memo.length; i++) {
Arrays.fill(memo[i], -2);
}
return dp(jobDifficulty, jobDifficulty.length - 1, d);
}

// split [0, index] to `count` parts
private int dp(int[] nums, int index, int count) {
// if [0, index] can't split to `count` parts, return -1(impossible)
if (index + 1 < count) {
return -1;
}
if (memo[index][count] != -2) { // if the memo store current value, return
return memo[index][count];
}
// split to one part, return the maximun
if (count == 1) {
var max = Integer.MIN_VALUE;
for (int i = 0; i <= index; i++) {
max = Math.max(max, nums[i]);
}
memo[index][count] = max;
return max;
}
for (int i = index - 1; i >= 0; i--) { // i represents the split point
var current = max(nums, i + 1, index); // get the maximum of right part
// we have a sub problem that split nums[0, i] to `count-1` part
var subProblem = dp(nums, i, count - 1);
if (subProblem != -1) { // if the sub problem has answer, update
}
}
}

private int max(int[] nums, int i, int j) {
var max = Integer.MIN_VALUE;
for (int k = i; k <= j; k++) {
max = Math.max(max, nums[k]);
}
return max;
}
}
``````

Complexity

Time Complexity: \$O(n^2*d)\$, \$n\$ is the length of \$jobDiffculty\$, we have a internal cycle to split the \$nums\$, whose time complexity is \$d\$, and the `max` function has a time complexity \$n\$, and when \$d=1\$, we have a cycle to calculate maximum.

Space complexity: \$O(n*d)\$, we use a memo to store the result to prevent repeat call.