##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1335.html

# 1335. Minimum Difficulty of a Job Schedule (Hard)

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th 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 in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th 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.


Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15


Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843


Constraints:

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

Related Topics:
Dynamic Programming

## Solution 1. DP

Let dp[d][i] be the answer for the subproblem with d days at ith job.

Let mx[i][j] be the maximum value in A[i..j].

dp[d][i] = min( dp[d-1][j-1] + mx[j][i] | d-1 <= j <= i )

// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(N^2 * D)
// Space: O(N^2 + ND)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size();
if (D > N) return -1;
vector<vector<LL>> mx(N, vector<LL>(N)), dp(D + 1, vector<LL>(N, 1e9));
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) mx[i][j] = *max_element(A.begin() + i, A.begin() + j + 1);
}
for (int i = 0; i < N; ++i) dp[1][i] = mx[0][i];
for (int d = 2; d <= D; ++d) {
for (int i = d - 1; i < N; ++i) {
for (int j = d - 1; j <= i; ++j) {
setMin(dp[d][i], dp[d - 1][j - 1] + mx[j][i]);
}
}
}
return dp[D][N - 1];
}
};


## Solution 2. DP

We can compute the mx while computing dp instead of computing mx array beforehand.

// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(N^2 * D)
// Space: O(ND)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size(), inf = 1e9;
if (D > N) return -1;
vector<vector<LL>> dp(D + 1, vector<LL>(N, inf));
for (int i = 0; i < N; ++i) dp[1][i] = i == 0 ? A[0] : max(dp[1][i - 1], (LL)A[i]);
for (int d = 2; d <= D; ++d) {
for (int i = d - 1; i < N; ++i) {
int mx = 0;
for (int j = i; j >= d - 1; --j) {
mx = max(mx, A[j]);
setMin(dp[d][i], dp[d - 1][j - 1] + mx);
}
}
}
return dp[D][N - 1];
}
};


## Solution 3. DP

Since dp[d][i] is dependent on dp[d-1][j-1] and j <= i, we can flip the loop direction and just need 1D dp array.

// OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(NND)
// Space: O(N)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size(), inf = 1e9;
if (D > N) return -1;
vector<LL> dp(N);
for (int i = 0; i < N; ++i) dp[i] = i == 0 ? A[0] : max(dp[i - 1], (LL)A[i]);
for (int d = 2; d <= D; ++d) {
for (int i = N - 1; i >= d - 1; --i) {
int mx = 0;
dp[i] = inf;
for (int j = i; j >= d - 1; --j) {
mx = max(mx, A[j]);
setMin(dp[i], dp[j - 1] + mx);
}
}
}
return dp[N - 1];
}
};


## Solution 4. DP + Monotonic Min Stack

TODO https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/discuss/490316/JavaC%2B%2BPython3-DP-O(nd)-Solution

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/discuss/495000/C%2B%2B-0ms!-O(d*n)-time-O(n)-space.-DP-%2B-MonotonicMinimum-Stack

• class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
if (jobDifficulty == null)
return -1;
int length = jobDifficulty.length;
if (length < d)
return -1;
if (length == d) {
int sum = 0;
for (int difficulty : jobDifficulty)
sum += difficulty;
return sum;
}
int[] maxDifficultyRight = new int[length];
maxDifficultyRight[length - 1] = jobDifficulty[length - 1];
for (int i = length - 2; i >= 0; i--)
maxDifficultyRight[i] = Math.max(maxDifficultyRight[i + 1], jobDifficulty[i]);
int[][] dp = new int[d][length];
dp[0][0] = jobDifficulty[0];
for (int i = 1; i <= length - d; i++)
dp[0][i] = Math.max(dp[0][i - 1], jobDifficulty[i]);
for (int i = 1; i < d; i++) {
int start = i, end = length - d + i;
int prevEnd = start - 1;
for (int j = start; j <= end; j++) {
dp[i][j] = dp[i - 1][j - 1] + jobDifficulty[j];
int max = jobDifficulty[j];
for (int k = j - 2; k >= prevEnd; k--) {
max = Math.max(max, jobDifficulty[k + 1]);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + max);
}
}
}
return dp[d - 1][length - 1];
}
}

############

class Solution {
public int minDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
final int inf = 1 << 30;
int[][] f = new int[n + 1][d + 1];
for (int[] g : f) {
Arrays.fill(g, inf);
}
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= d; ++j) {
int mx = 0;
for (int k = i; k > 0; --k) {
mx = Math.max(mx, jobDifficulty[k - 1]);
f[i][j] = Math.min(f[i][j], f[k - 1][j - 1] + mx);
}
}
}
return f[n][d] < inf ? f[n][d] : -1;
}
}

• // OJ: https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/
// Time: O(N^2 * D)
// Space: O(N^2 + ND)
class Solution {
typedef long long LL;
inline void setMin(LL &a, LL b) { a = min(a, b); }
public:
int minDifficulty(vector<int>& A, int D) {
int N = A.size();
if (D > N) return -1;
vector<vector<LL>> mx(N, vector<LL>(N)), dp(D + 1, vector<LL>(N, 1e9));
for (int i = 0; i < N; ++i) {
for (int j = i; j < N; ++j) mx[i][j] = *max_element(A.begin() + i, A.begin() + j + 1);
}
for (int i = 0; i < N; ++i) dp[1][i] = mx[0][i];
for (int d = 2; d <= D; ++d) {
for (int i = d - 1; i < N; ++i) {
for (int j = d - 1; j <= i; ++j) {
setMin(dp[d][i], dp[d - 1][j - 1] + mx[j][i]);
}
}
}
return dp[D][N - 1];
}
};

• class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
f = [[inf] * (d + 1) for _ in range(n + 1)]
f[0][0] = 0
for i, x in enumerate(jobDifficulty, 1):
for j in range(1, d + 1):
mx = 0
for k in range(i, 0, -1):
mx = max(mx, jobDifficulty[k - 1])
f[i][j] = min(f[i][j], f[k - 1][j - 1] + mx)
return f[n][d] if f[n][d] != inf else -1


• func minDifficulty(jobDifficulty []int, d int) int {
n := len(jobDifficulty)
f := make([][]int, n+1)
const inf = 1 << 30
for i := range f {
f[i] = make([]int, d+1)
for j := range f[i] {
f[i][j] = inf
}
}
f[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= d; j++ {
mx := 0
for k := i; k > 0; k-- {
mx = max(mx, jobDifficulty[k-1])
f[i][j] = min(f[i][j], f[k-1][j-1]+mx)
}
}
}
if f[n][d] == inf {
return -1
}
return f[n][d]
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

• function minDifficulty(jobDifficulty: number[], d: number): number {
const n = jobDifficulty.length;
const inf = 1 << 30;
const f: number[][] = new Array(n + 1)
.fill(0)
.map(() => new Array(d + 1).fill(inf));
f[0][0] = 0;
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= Math.min(d, i); ++j) {
let mx = 0;
for (let k = i; k > 0; --k) {
mx = Math.max(mx, jobDifficulty[k - 1]);
f[i][j] = Math.min(f[i][j], f[k - 1][j - 1] + mx);
}
}
}
return f[n][d] < inf ? f[n][d] : -1;
}