NeetCode #753LC-1335Hard2-D Dynamic Programming
← Back to All Problems#753 · #1335 · Minimum Difficulty of a Job Schedule(工作计划的最低难度)
📌 Problem Statement & Constraints
You have
jobDifficulty and d days. Split the jobs, in the given order, into exactly d non-empty consecutive groups. A day's difficulty is the maximum job in it, and the schedule's difficulty is the sum over days. Return the minimum schedule difficulty, or -1 if impossible. Constraints: 1 <= d <= jobDifficulty.length <= 300, 0 <= jobDifficulty[i] <= 1000.💡 Core Algorithmic Approaches
- Let
dp[day][i]be the minimum total difficulty for the firstijobs split intodaydays. - A day is a contiguous block, so if the last day starts at index
j, its difficulty ismax(jobDifficulty[j:i]). - Then
dp[day][i] = min over j of (dp[day-1][j] + max(jobDifficulty[j:i])), withjranging over valid starts for the last day. - Extending the maximum backwards as
jdecreases makes the inner maximum O(1), so the total is O(n^2 * d).
💻 Benchmark Python3 Implementation
class Solution:
def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
n = len(jobDifficulty)
if n < d:
return -1 # every day needs at least one job
INF = float("inf")
dp = [INF] * (n + 1)
dp[0] = 0
for day in range(1, d + 1):
nxt = [INF] * (n + 1)
for i in range(day, n + 1):
hardest = 0
# j is the start index of the current (last) day
for j in range(i - 1, day - 2, -1):
hardest = max(hardest, jobDifficulty[j])
if dp[j] < INF:
nxt[i] = min(nxt[i], dp[j] + hardest)
dp = nxt
return dp[n]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 * d): each day's layer considers O(n^2) (start, end) pairs.
💾 Space Complexity
O(n): one rolling array.
⚠️ Interview Pitfalls & Follow-ups
- Returning 0 when
n < d: the schedule is impossible, so the answer is -1, not 0. - Using the sum instead of the max for a day: a day's difficulty is the maximum job in it, not the total.
- Allowing an empty day: the inner loop's lower bound
day - 1guarantees each earlier day holds at least one job. - Recomputing
max(jobDifficulty[j:i])from scratch: extending the maximum backwards asjdecreases gives it in O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.