# 1335. Minimum Difficulty of a Job Schedule

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`

``````class Solution {
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (d > n) return -1;
vector<vector<int>> dp(d, vector<int>(n, INT_MAX));
dp[0][0] = jobDifficulty[0];
for (int j = 1; j < n; ++j) {
dp[0][j] = max(dp[0][j - 1], jobDifficulty[j]);
}
for (int i = 1; i < d; ++i) {
for (int j = i; j < n; ++j) {
int curMax = jobDifficulty[j];
for (int k = j; k >= i; --k) {
curMax = max(curMax, jobDifficulty[k]);
dp[i][j] = min(dp[i][j], dp[i - 1][k - 1] + curMax);
}
}
}
return dp[d - 1][n - 1];
}
};
``````

``````class Solution {
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (d > n) return -1;
vector<vector<int>> memo(d + 1, vector<int>(n, -1));
return dfs(jobDifficulty, d, 0, memo);
}
int dfs(vector<int>& jobDifficulty, int dayLeft, int idx, vector<vector<int>>& memo) {
int n = jobDifficulty.size();
if (dayLeft == 0 && idx == n) return 0;
if (dayLeft == 0 || idx == n) return INT_MAX;
if (memo[dayLeft][idx] != -1) return memo[dayLeft][idx];
int curMax = jobDifficulty[idx], res = INT_MAX;
for (int i = idx; i < n; ++i) {
curMax = max(curMax, jobDifficulty[i]);
int t = dfs(jobDifficulty, dayLeft - 1, i + 1, memo);
if (t != INT_MAX) {
res = min(res, t + curMax);
}
}
return memo[dayLeft][idx] = res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1335

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/solutions/490316/java-c-python3-dp-o-nd-solution/

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/solutions/944828/short-dp-solution-with-highly-detailed-step-by-step-explanation/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation