Minimum Difficulty of a Job Schedule: DP with Day Partitions

You have n jobs and d days. Every job has a difficulty rating. You must schedule all jobs so that at least one job is done each day, and the jobs must be done in the original order (you cannot reorder them). Each day, you do a contiguous block of jobs, and the difficulty of that day is the maximum difficulty among the jobs you did. The total difficulty is the sum of each day's difficulty. Find the minimum total difficulty across all valid schedules. If it is impossible (fewer jobs than days), return -1.

This is LeetCode 1335: Minimum Difficulty of a Job Schedule, and it is a clean example of partition DP. The problem boils down to splitting an array into exactly d contiguous groups and minimizing the sum of each group's maximum. Once you see it that way, the DP formulation falls into place.

Why this problem matters

Partition DP is a pattern that shows up across many hard problems. The idea is always the same: you have a sequence, you need to split it into a fixed number of contiguous segments, and you want to optimize some cost function over those segments. In this case the cost of a segment is its maximum value, and you want to minimize the total.

What makes this problem a great learning target is that the partition structure is the entire challenge. There is no tricky data structure involved, no complicated math. If you understand how to set up dp[i][j] and enumerate split points, you have the solution. That same skill transfers directly to problems like Palindrome Partitioning II, Split Array Largest Sum, and Burst Balloons.

The problem also reinforces a key DP skill: choosing the right state definition. Once you define dp[i][j] as the minimum difficulty to schedule jobs 0..i over j days, the transition writes itself. Getting comfortable with 2D DP states that combine "how far along the sequence" with "how many resources used" is essential for tackling harder DP problems.

The approach

Define dp[i][j] as the minimum total difficulty to schedule jobs 0 through i using exactly j days.

Base case: dp[i][1] = max(jobs[0], jobs[1], ..., jobs[i]). If you have only one day, you must do all jobs in a single batch, and the difficulty is the maximum.

Transition: For j > 1, try every possible split point k where day j covers jobs k+1 through i:

dp[i][j] = min over all valid k of (dp[k][j-1] + max(jobs[k+1..i]))

This says: schedule jobs 0..k over j-1 days (that is dp[k][j-1]), then do jobs k+1..i on the last day (costing max(jobs[k+1..i])). Try every valid k and pick the one that gives the smallest total.

The constraint is that k must be at least j-2 (so the first j-1 days each have at least one job) and at most i-1 (so the last day has at least one job).

def min_difficulty(job_difficulty, d):
    n = len(job_difficulty)
    if n < d:
        return -1

    dp = [[float('inf')] * (d + 1) for _ in range(n)]

    running_max = 0
    for i in range(n):
        running_max = max(running_max, job_difficulty[i])
        dp[i][1] = running_max

    for j in range(2, d + 1):
        for i in range(j - 1, n):
            max_so_far = 0
            for k in range(i, j - 2, -1):
                max_so_far = max(max_so_far, job_difficulty[k])
                dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + max_so_far)

    return dp[n - 1][d]

Walking through the DP table

The table fills column by column (day by day). The first column is easy: with one day, every prefix has difficulty equal to its running maximum. For the second column, each cell tries all possible split points and picks the one that minimizes the total. The answer lives in the bottom-right corner: dp[5][2] = 7.

In this example, the optimal split puts jobs [6, 5, 4, 3, 2] on day 1 (max = 6) and job [1] on day 2 (max = 1), giving a total difficulty of 7. You can verify that no other partition of 6 jobs into 2 days produces a lower total.

Here is the final clean solution:

def min_difficulty(job_difficulty, d):
    n = len(job_difficulty)
    if n < d:
        return -1

    dp = [[float('inf')] * (d + 1) for _ in range(n)]

    running_max = 0
    for i in range(n):
        running_max = max(running_max, job_difficulty[i])
        dp[i][1] = running_max

    for j in range(2, d + 1):
        for i in range(j - 1, n):
            max_so_far = 0
            for k in range(i, j - 2, -1):
                max_so_far = max(max_so_far, job_difficulty[k])
                dp[i][j] = min(dp[i][j], dp[k - 1][j - 1] + max_so_far)

    return dp[n - 1][d]

Complexity analysis

Time: O(n^2 * d). For each of the d days, for each of the n ending positions, we try up to n split points. The triple nested loop gives O(n^2 * d).

Space: O(n * d). The 2D DP table has n rows and d columns. You can optimize to O(n) per day layer by only keeping two columns at a time, since day j only depends on day j-1.

For very large inputs, a monotonic stack optimization can bring the time down to O(n * d), but the O(n^2 * d) version is sufficient for LeetCode's constraints (n and d up to 300).

Edge cases to watch for

• n < d: impossible to schedule, since each day needs at least one job. Return -1.
• n = d: each day gets exactly one job. The total difficulty is the sum of all job difficulties.
• d = 1: one day, all jobs in a single batch. Return the maximum job difficulty.
• All equal difficulties: every partition has the same total (d * difficulty). Return that value.
• Decreasing difficulties like [6, 5, 4, 3, 2, 1]: the optimal strategy pushes as many small jobs to the last day as possible, since the first day's max is unavoidably 6.
• Single job: n = 1, d = 1. Return job_difficulty[0].

The building blocks

This problem is built on partition DP, the pattern of splitting a sequence into a fixed number of contiguous segments to optimize a cost function. The skeleton is always the same:

• State: dp[i][j] = optimal cost for the first i+1 elements split into j groups
• Transition: try every split point for the last group, combine with the optimal cost for the remaining groups
• Base case: one group means the cost function applied to the entire prefix

This same skeleton powers several other problems:

• Split Array Largest Sum (LeetCode 410): partition an array into m groups, minimize the largest group sum. Same structure, different cost function (sum instead of max).
• Palindrome Partitioning II (LeetCode 132): partition a string into the fewest palindromes. The "number of groups" is what you are minimizing rather than fixing.
• Burst Balloons (LeetCode 312): partition-style DP where you choose which element to remove last in each segment.

Once you internalize the partition DP skeleton, these problems become variations on a single theme. You set up the state, enumerate split points, and apply the cost function. The differences are in the details, not the structure.

From understanding to recall

You have traced through the DP table and the logic makes sense. But will you be able to write the triple-nested loop with the correct bounds in an interview? Will you remember to iterate k from right to left so you can build up the running maximum? Will you handle the n < d edge case before touching the DP table?

Understanding and recall are different skills. The gap between "I get it" and "I can write it cold" is bigger than most people expect. Spaced repetition closes that gap. You revisit the partition DP skeleton at increasing intervals, writing the state definition and transition from scratch each time. After a few reps, the pattern of "enumerate split points, combine prefix cost with suffix cost" becomes second nature.

The partition DP pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Jump Game - A greedy problem where understanding array partitioning and reachability builds intuition for sequence-based DP
• Coin Change - The classic bottom-up DP problem, showing the same "fill a table from smaller subproblems" approach with a simpler 1D state
• Maximum Product Subarray - Another DP problem where tracking a running value (min/max) through the array is the key optimization trick