236. Minimum Difficulty of a Job Schedule

🔗 LeetCode Problem: 1335. Minimum Difficulty of a Job Schedule
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, Array, DP - Subsequences

Problem Statement

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 job difficulty of that day.

Given an array of integers jobDifficulty and an integer d. 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

---

🔍 Let's Discover the Pattern Together

Start with Small Examples

Let's not jump to the solution. Let's understand what's really happening by trying small examples:

Example 1: jobDifficulty = [6, 5, 4, 3, 2, 1], d = 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
We have 6 jobs, need to split into 2 days.
Jobs are dependent: must do in order!

Key constraint: At least 1 job per day

Possible splits:
  Day 1: [6] Day 2: [5,4,3,2,1]
    Difficulty: max(6) + max(5,4,3,2,1) = 6 + 5 = 11

  Day 1: [6,5] Day 2: [4,3,2,1]
    Difficulty: max(6,5) + max(4,3,2,1) = 6 + 4 = 10

  Day 1: [6,5,4] Day 2: [3,2,1]
    Difficulty: max(6,5,4) + max(3,2,1) = 6 + 3 = 9

  Day 1: [6,5,4,3] Day 2: [2,1]
    Difficulty: max(6,5,4,3) + max(2,1) = 6 + 2 = 8

  Day 1: [6,5,4,3,2] Day 2: [1]
    Difficulty: max(6,5,4,3,2) + max(1) = 6 + 1 = 7 ✓ MINIMUM!

Answer: 7

Example 2: jobDifficulty = [9, 9, 9], d = 4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
We have 3 jobs, need 4 days.

Problem: We MUST do at least 1 job per day!
  3 jobs < 4 days → IMPOSSIBLE!

Answer: -1

Example 3: jobDifficulty = [1, 1, 1], d = 3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
3 jobs, 3 days → exactly 1 job per day!

Only possible split:
  Day 1: [1] → difficulty = 1
  Day 2: [1] → difficulty = 1
  Day 3: [1] → difficulty = 1

Total: 1 + 1 + 1 = 3

Answer: 3

Notice the Pattern

Key observations:

1. Jobs must be done IN ORDER (dependent)
   Can't skip or rearrange!

2. Must do at least 1 job per day
   → Need: n jobs >= d days
   → If n < d, return -1

3. Day's difficulty = MAXIMUM job difficulty that day
   Not sum, but MAX!

4. Total difficulty = SUM of each day's difficulty

5. We need to find the OPTIMAL way to split jobs across days
   This is a PARTITIONING problem!

The Partitioning Intuition

Think of it as placing dividers:

Jobs: [6, 5, 4, 3, 2, 1]
Days: d = 2

We need to place (d-1) = 1 divider:

  [6, 5, 4, 3, 2 | 1]
   Day 1: max=6   Day 2: max=1
   Total: 6 + 1 = 7 ✓

Try different divider positions:
  [6 | 5, 4, 3, 2, 1] → 6 + 5 = 11
  [6, 5 | 4, 3, 2, 1] → 6 + 4 = 10
  [6, 5, 4 | 3, 2, 1] → 6 + 3 = 9
  [6, 5, 4, 3 | 2, 1] → 6 + 2 = 8
  [6, 5, 4, 3, 2 | 1] → 6 + 1 = 7 ✓ BEST!

Try all divider placements, find minimum!

---

💡 The AHA Moment - It's a DP Problem!

Why Recursion/DP?

For each position, we make a decision:
  "Should we end the current day here?"

Example: jobDifficulty = [6,5,4,3,2,1], d = 2

At index 0 (job 6):
  Option 1: Finish day 1 here → [6] | rest
  Option 2: Continue day 1 → [6,5,...] | rest
  ...

For EACH position and remaining days:
  Try all possible ways to partition
  Pick the minimum!

This is OVERLAPPING SUBPROBLEMS!
  → Perfect for DP! 🎯

The Recursive Thinking

Define: minDifficulty(index, daysLeft)
  = Minimum difficulty starting from index with daysLeft days

For current day, we can take:
  - Just job[index]
  - job[index] and job[index+1]
  - job[index], job[index+1], job[index+2]
  - ...
  - All remaining jobs (if daysLeft == 1)

For each option:
  maxDifficulty = max job difficulty in current day
  remaining = minDifficulty(nextIndex, daysLeft-1)
  total = maxDifficulty + remaining

Return minimum across all options! ✓

---

🔴 Approach 1: Recursion (Brute Force)

📐 Function Definition

Function Signature:

int minDifficulty(int index, int daysLeft, int[] jobDifficulty)

What does this function compute? - Input index: Current job position (start of current day) - Input daysLeft: Number of days remaining (including today) - Input jobDifficulty: Array of job difficulties - Output: Minimum difficulty to complete jobs from index onwards using daysLeft days

What does the recursive call represent? - For current day, we decide how many jobs to do (at least 1) - For each choice of jobs for today: - Calculate max difficulty for today - Recursively solve for remaining jobs with (daysLeft - 1) days - Add today's max to recursive result - Return minimum across all choices

The Recursive Structure:

Base case 1: daysLeft == 1
  → Must finish ALL remaining jobs today
  → return max(jobDifficulty[index...n-1])

Base case 2: index == n (no jobs left)
  → If daysLeft == 0: return 0 (success!)
  → If daysLeft > 0: return INFINITY (invalid, need more jobs)

For current day:
  Try taking 1 job, 2 jobs, 3 jobs, ..., (n-index-daysLeft+1) jobs

  For each choice:
    todayMax = max difficulty of jobs taken today
    restMin = minDifficulty(nextIndex, daysLeft-1)
    total = todayMax + restMin

  Return minimum

Why this works:

We systematically try all valid partitions:
  - At each step, choose jobs for current day
  - Recursively solve for remaining
  - Track minimum difficulty

This explores all possibilities!

💡 Intuition

Think of assigning jobs day by day:

jobDifficulty = [6, 5, 4], d = 2

Day 1 (2 days left):
  Take 1 job [6]:
    Day 1 max = 6
    Remaining: [5,4] with 1 day
    Day 2 max = 5
    Total: 6 + 5 = 11

  Take 2 jobs [6,5]:
    Day 1 max = 6
    Remaining: [4] with 1 day
    Day 2 max = 4
    Total: 6 + 4 = 10 ✓ BETTER!

Try all splits, pick minimum!

📝 Implementation

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;

        // Impossible if fewer jobs than days
        if (n < d) return -1;

        return helper(0, d, jobDifficulty);
    }

    private int helper(int index, int daysLeft, int[] jobDifficulty) {
        int n = jobDifficulty.length;

        // Base case: last day, must finish all remaining jobs
        if (daysLeft == 1) {
            int max = 0;
            for (int i = index; i < n; i++) {
                max = Math.max(max, jobDifficulty[i]);
            }
            return max;
        }

        int minDiff = Integer.MAX_VALUE;
        int currentMax = 0;

        // Try taking different number of jobs for current day
        // Must leave at least (daysLeft - 1) jobs for remaining days
        for (int i = index; i < n - daysLeft + 1; i++) {
            // Update max for current day
            currentMax = Math.max(currentMax, jobDifficulty[i]);

            // Recursively solve for remaining jobs
            int restDiff = helper(i + 1, daysLeft - 1, jobDifficulty);

            // Total difficulty
            minDiff = Math.min(minDiff, currentMax + restDiff);
        }

        return minDiff;
    }
}

🔍 Detailed Dry Run: jobDifficulty = [6,5,4], d = 2

Initial call: helper(0, 2, [6,5,4])

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(index=0, daysLeft=2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  Jobs: [6,5,4], 2 days left
  Must leave at least 1 job for day 2

  Try i=0 (take job 0 only, [6]):
    currentMax = 6

    helper(index=1, daysLeft=1):
      Last day! Take all remaining [5,4]
      max = max(5, 4) = 5
      return 5

    restDiff = 5
    total = 6 + 5 = 11
    minDiff = min(INF, 11) = 11

  Try i=1 (take jobs 0-1, [6,5]):
    currentMax = max(6, 5) = 6

    helper(index=2, daysLeft=1):
      Last day! Take all remaining [4]
      max = 4
      return 4

    restDiff = 4
    total = 6 + 4 = 10
    minDiff = min(11, 10) = 10 ✓

  Can't try i=2 (would leave 0 jobs for day 2)

  return 10

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 10 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Optimal partition:
  Day 1: [6,5] → max = 6
  Day 2: [4] → max = 4
  Total: 10

Why This Is Slow

Time Complexity: O(n^d)
  For each of d days:
    Try n different split points
  Total: n × n × ... (d times) = n^d

For n=300, d=10:
  300^10 = astronomical!
  WAY TOO SLOW! ❌

We need memoization! →

📊 Complexity Analysis

Time: O(n^d) - Exponential!
Space: O(d) - Recursion stack depth

---

🟡 Approach 2: Memoization (Top-Down DP)

🎯 What Do We Memoize?

Our recursive function:
  helper(index, daysLeft)

State:
  - index: where we start (0 to n-1)
  - daysLeft: how many days remaining (1 to d)

Total states: n × d

memo[index][daysLeft] = minimum difficulty for this state

This is PERFECT for memoization! ✓

📐 Function Definition with Memoization

Variables we track: - memo[index][daysLeft] = Minimum difficulty starting from index with daysLeft days - If computed, reuse it! - If not computed (-1), compute and cache it!

Purpose: - Same recursive logic - But CACHE results for each (index, daysLeft) state - Each unique state solved only ONCE!

Key Understanding:

Without memo:
  helper(5, 3) called multiple times
  Each time: recompute everything ✗

With memo:
  helper(5, 3) called first time → compute, cache
  Called again → return cached result immediately ✓

This transforms O(n^d) → O(n² × d)!

💡 Intuition

Think of it as a lookup table:

State: (index=5, daysLeft=3)
Question: "Min difficulty from job 5 with 3 days?"

First time:
  Compute by trying all possibilities
  Result: 42
  Store in memo[5][3] = 42

Second time same state:
  Check memo[5][3]
  Found! Return 42 immediately
  No recomputation!

The memo saves massive amounts of work!

📝 Implementation

class Solution {
    private int[][] memo;

    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;

        if (n < d) return -1;

        // memo[index][daysLeft]
        memo = new int[n][d + 1];

        // Initialize with -1 (not computed)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= d; j++) {
                memo[i][j] = -1;
            }
        }

        return helper(0, d, jobDifficulty);
    }

    private int helper(int index, int daysLeft, int[] jobDifficulty) {
        int n = jobDifficulty.length;

        // Base case: last day
        if (daysLeft == 1) {
            int max = 0;
            for (int i = index; i < n; i++) {
                max = Math.max(max, jobDifficulty[i]);
            }
            return max;
        }

        // Check memo
        if (memo[index][daysLeft] != -1) {
            return memo[index][daysLeft];
        }

        int minDiff = Integer.MAX_VALUE;
        int currentMax = 0;

        // Try different splits
        for (int i = index; i < n - daysLeft + 1; i++) {
            currentMax = Math.max(currentMax, jobDifficulty[i]);

            int restDiff = helper(i + 1, daysLeft - 1, jobDifficulty);

            minDiff = Math.min(minDiff, currentMax + restDiff);
        }

        // Cache result
        memo[index][daysLeft] = minDiff;
        return minDiff;
    }
}

🔍 Detailed Dry Run: jobDifficulty = [6,5,4,3], d = 2

memo = int[4][3] (all -1 initially)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
helper(0, 2):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
  Check memo[0][2] = -1 (not computed)

  Try i=0 ([6]):
    currentMax = 6

    helper(1, 1):
      Last day! max([5,4,3]) = 5
      return 5

    total = 6 + 5 = 11
    minDiff = 11

  Try i=1 ([6,5]):
    currentMax = 6

    helper(2, 1):
      Last day! max([4,3]) = 4
      return 4

    total = 6 + 4 = 10
    minDiff = min(11, 10) = 10

  Try i=2 ([6,5,4]):
    currentMax = 6

    helper(3, 1):
      Last day! max([3]) = 3
      return 3

    total = 6 + 3 = 9
    minDiff = min(10, 9) = 9 ✓

  memo[0][2] = 9
  return 9

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: 9 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Optimal partition:
  Day 1: [6,5,4] → max = 6
  Day 2: [3] → max = 3
  Total: 9

Memo entries saved:
  memo[0][2] = 9
  (Base cases computed directly, not cached)

Why Memoization Works

KEY INSIGHT:
  Same (index, daysLeft) state appears multiple times

With memo: compute once, reuse many times!

Example:
  From different paths, we might reach:
    (index=5, daysLeft=3)

  First time: compute, cache
  Later times: instant lookup!

Transforms exponential → polynomial!

📊 Complexity Analysis

Time Complexity: O(n² × d)

States: n × d
For each state: try n splits
Total: O(n² × d)

For n=300, d=10:
  300² × 10 = 900,000 operations
  Manageable! ✓

Space Complexity: O(n × d)

Memo array: n × d
Recursion stack: O(d)
Total: O(n × d)

---

🟢 Approach 3: Bottom-Up DP - COMPLETE LOOP EXPLANATION

🎯 Understanding the State

dp[i][day] means:
  "Minimum difficulty to complete the FIRST i jobs
   using exactly 'day' days"

Example:
  jobDifficulty = [6, 5, 4, 3]
  indices:         0  1  2  3

  dp[2][1] = "First 2 jobs [6,5] in 1 day"
    → Must take both in same day
    → difficulty = max(6,5) = 6

  dp[3][2] = "First 3 jobs [6,5,4] in 2 days"
    → Split somehow into 2 days
    → Try: Day1=[6], Day2=[5,4] → 6+5=11
    → Try: Day1=[6,5], Day2=[4] → 6+4=10 ✓
    → dp[3][2] = 10

KEY: i represents "how many jobs" (1-indexed in DP)
     Array indices are 0-indexed: job[0], job[1], ...

🧒 Base Case Derivation

BASE CASE in TOP-DOWN:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

if (daysLeft == 1):
  Take all remaining jobs
  return max of those jobs

BOTTOM-UP TRANSLATION:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

dp[0][0] = 0
  → 0 jobs in 0 days
  → No difficulty
  → This is our starting point!

All other dp[i][j] = INFINITY initially
  → Mark as "not yet computed"
  → Will be updated during computation

---

🔁 COMPLETE LOOP EXPLANATION - Step by Step

Loop 1: Outer Loop - for (int i = 1; i <= n; i++)

WHAT IT DOES:
  Iterates through number of jobs processed

WHAT i REPRESENTS:
  i = how many jobs we've completed
  i = 1: First 1 job  → job[0]
  i = 2: First 2 jobs → job[0], job[1]
  i = 3: First 3 jobs → job[0], job[1], job[2]
  ...
  i = n: All n jobs

WHY START AT 1:
  dp[0][0] = 0 is base case (no jobs, no days)
  We build from 1 job upwards

WHY END AT n:
  We want dp[n][d] (all n jobs in d days)
  That's our final answer!

VISUAL:
  jobs = [6, 5, 4, 3]

  i=1: Process dp[1][...] → "First 1 job [6]"
  i=2: Process dp[2][...] → "First 2 jobs [6,5]"
  i=3: Process dp[3][...] → "First 3 jobs [6,5,4]"
  i=4: Process dp[4][...] → "All 4 jobs [6,5,4,3]"

Loop 2: Middle Loop - for (int day = 1; day <= Math.min(i, d); day++)

WHAT IT DOES:
  For current i jobs, try using different number of days

WHAT day REPRESENTS:
  day = how many days we're using
  day = 1: All i jobs in 1 day
  day = 2: All i jobs in 2 days
  ...

WHY START AT 1:
  Must use at least 1 day!

WHY END AT Math.min(i, d):
  Can't use more days than jobs! (need 1 job per day)
  Can't use more than d total days!

  Example: i=2 jobs, d=5 total days
    → Can only use up to 2 days (min(2,5)=2)
    → Can't use 3,4,5 days (not enough jobs!)

VISUAL:
  i=3 (3 jobs), d=2

  day=1: dp[3][1] → "3 jobs in 1 day"
  day=2: dp[3][2] → "3 jobs in 2 days"
  (Stop at 2 because d=2)

  i=2 (2 jobs), d=5

  day=1: dp[2][1] → "2 jobs in 1 day"
  day=2: dp[2][2] → "2 jobs in 2 days"
  (Stop at 2 because i=2, can't use more days than jobs!)

Loop 3: Inner Loop - for (int j = i - 1; j >= day - 1; j--)

THIS IS THE TRICKY ONE! Let's break it down completely:

WHAT IT DOES:
  Decides where the LAST day (day 'day') starts

WHAT j REPRESENTS:
  j = starting position of the LAST day

  If we're computing dp[i][day]:
    - We have i jobs total: jobs[0...i-1]
    - We're using 'day' days
    - The last day (day number 'day') starts at position j
    - The last day contains jobs: jobs[j...i-1]
    - Previous days contain jobs: jobs[0...j-1]

VISUAL EXPLANATION:

  Example: i=4, day=2
    Jobs: [6, 5, 4, 3]
    Index: 0  1  2  3

    Question: "4 jobs in 2 days"

    Try j=3:
      Last day: jobs[3...3] = [3]
      Previous: jobs[0...2] = [6,5,4] using (day-1)=1 day

      |------ Day 1 -------|Day 2|
      [6,      5,      4,     3  ]
       0       1       2      3
                              ↑
                              j=3 (last day starts here)

    Try j=2:
      Last day: jobs[2...3] = [4,3]
      Previous: jobs[0...1] = [6,5] using (day-1)=1 day

      |---- Day 1 ----|-- Day 2 --|
      [6,      5,        4,     3  ]
       0       1         2      3
                         ↑
                         j=2 (last day starts here)

    Try j=1:
      Last day: jobs[1...3] = [5,4,3]
      Previous: jobs[0...0] = [6] using (day-1)=1 day

      |Day 1 |------- Day 2 -------|
      [6,       5,      4,      3   ]
       0        1       2       3
                ↑
                j=1 (last day starts here)

WHY START AT i-1:
  The last day can start at the LAST job (i-1)
  This means: last day takes only 1 job

  Example: i=4
    j=3: Last day = job[3] (just last job)

WHY END AT day-1:
  We need to leave at least (day-1) jobs for previous days!
  Previous days need (day-1) jobs minimum (1 job per day)

  Example: i=4, day=2
    Need (day-1)=1 job for day 1
    So j can go down to 1 (leaving job[0] for day 1)
    Can't be j=0 (would leave no jobs for day 1!)

  Example: i=5, day=3
    Need (day-1)=2 jobs for days 1 and 2
    So j can go down to 2 (leaving jobs[0,1] for days 1,2)
    Can't be j=1 or j=0 (not enough jobs for 2 days!)

WHY GO BACKWARDS (j--):
  We're computing maxDifficulty incrementally!

  Start from j=i-1 (1 job on last day)
  As we decrease j (j--, j--, ...)
    → Add more jobs to last day
    → Update maxDifficulty efficiently

  Example:
    j=3: maxDiff = job[3] = 3
    j=2: maxDiff = max(job[2], 3) = max(4,3) = 4
    j=1: maxDiff = max(job[1], 4) = max(5,4) = 5

  Efficient! Don't recompute max each time!

COMPLETE EXAMPLE:
  jobs = [6, 5, 4, 3], i=4, day=2

  Loop: j from 3 down to 1

  j=3:
    Last day: [3]
    maxDifficulty = 3
    Previous: dp[3][1] = "3 jobs in 1 day" = 6
    Total: dp[3][1] + 3 = 6 + 3 = 9

  j=2:
    Last day: [4, 3]
    maxDifficulty = max(3, 4) = 4
    Previous: dp[2][1] = "2 jobs in 1 day" = 6
    Total: dp[2][1] + 4 = 6 + 4 = 10

  j=1:
    Last day: [5, 4, 3]
    maxDifficulty = max(4, 5) = 5
    Previous: dp[1][1] = "1 job in 1 day" = 6
    Total: dp[1][1] + 5 = 6 + 5 = 11

  dp[4][2] = min(9, 10, 11) = 9 ✓

The Complete Picture

NESTED LOOPS SUMMARY:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

for i = 1 to n:               // How many jobs
  for day = 1 to min(i, d):   // How many days
    for j = i-1 down to day-1: // Where last day starts

      Last day: jobs[j...i-1]
      Previous: jobs[0...j-1] using (day-1) days

      maxDiff = max(jobs[j...i-1])
      dp[i][day] = min(dp[i][day], 
                       dp[j][day-1] + maxDiff)

This tries ALL valid partitions! ✓

---

📝 Complete Implementation with Comments

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;

        // Impossible if fewer jobs than days
        if (n < d) return -1;

        // dp[i][day] = min difficulty for first i jobs in 'day' days
        int[][] dp = new int[n + 1][d + 1];

        // Initialize with large value (infinity)
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= d; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        // Base case: 0 jobs, 0 days = no difficulty
        dp[0][0] = 0;

        // LOOP 1: Process jobs one by one
        // i = number of jobs we've completed
        for (int i = 1; i <= n; i++) {

            // LOOP 2: Try using different number of days
            // day = number of days we're using for these i jobs
            // Can't use more days than jobs (need 1 job per day)
            // Can't use more than d total days
            for (int day = 1; day <= Math.min(i, d); day++) {

                int maxDifficulty = 0;

                // LOOP 3: Try different starting positions for LAST day
                // j = where the last day (day 'day') starts
                // Last day takes jobs [j...i-1]
                // Previous days took jobs [0...j-1] using (day-1) days
                //
                // Start: j = i-1 (last day takes only last job)
                // End: j = day-1 (leave at least day-1 jobs for previous days)
                // Direction: backwards to compute maxDifficulty efficiently
                for (int j = i - 1; j >= day - 1; j--) {

                    // Update max difficulty for current last day
                    // As j decreases, we add more jobs to last day
                    // job[j] is the newly added job
                    maxDifficulty = Math.max(maxDifficulty, jobDifficulty[j]);

                    // Check if previous state is valid
                    if (dp[j][day - 1] != Integer.MAX_VALUE) {
                        // Total = previous days + current last day
                        dp[i][day] = Math.min(dp[i][day], 
                                             dp[j][day - 1] + maxDifficulty);
                    }
                }
            }
        }

        // Return answer for all n jobs in d days
        return dp[n][d] == Integer.MAX_VALUE ? -1 : dp[n][d];
    }
}

---

🔍 Complete Dry Run with ALL Loops

jobDifficulty = [6, 5, 4], d = 2
n = 3

Initialize:
  dp[all] = INF
  dp[0][0] = 0

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LOOP 1: i = 1 (First 1 job: [6])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  LOOP 2: day = 1 (1 job in 1 day)

    LOOP 3: j from 0 down to 0 (day-1 = 0)

      j=0:
        Last day: jobs[0...0] = [6]
        maxDifficulty = 6
        Previous: dp[0][0] = 0
        dp[1][1] = min(INF, 0 + 6) = 6

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LOOP 1: i = 2 (First 2 jobs: [6, 5])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  LOOP 2: day = 1 (2 jobs in 1 day)

    LOOP 3: j from 1 down to 0

      j=1:
        Last day: jobs[1...1] = [5]
        maxDifficulty = 5
        Previous: dp[1][0] = INF (invalid)
        Skip!

      j=0:
        Last day: jobs[0...1] = [6, 5]
        maxDifficulty = max(5, 6) = 6
        Previous: dp[0][0] = 0
        dp[2][1] = min(INF, 0 + 6) = 6

  LOOP 2: day = 2 (2 jobs in 2 days)

    LOOP 3: j from 1 down to 1 (day-1 = 1)

      j=1:
        Last day: jobs[1...1] = [5]
        maxDifficulty = 5
        Previous: dp[1][1] = 6
        dp[2][2] = min(INF, 6 + 5) = 11

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
LOOP 1: i = 3 (All 3 jobs: [6, 5, 4])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  LOOP 2: day = 1 (3 jobs in 1 day)

    LOOP 3: j from 2 down to 0

      j=2:
        Last day: jobs[2...2] = [4]
        maxDifficulty = 4
        Previous: dp[2][0] = INF
        Skip!

      j=1:
        Last day: jobs[1...2] = [5, 4]
        maxDifficulty = max(4, 5) = 5
        Previous: dp[1][0] = INF
        Skip!

      j=0:
        Last day: jobs[0...2] = [6, 5, 4]
        maxDifficulty = max(5, 6) = 6
        Previous: dp[0][0] = 0
        dp[3][1] = min(INF, 0 + 6) = 6

  LOOP 2: day = 2 (3 jobs in 2 days)

    LOOP 3: j from 2 down to 1 (day-1 = 1)

      j=2:
        Last day: jobs[2...2] = [4]
        maxDifficulty = 4
        Previous: dp[2][1] = 6
        dp[3][2] = min(INF, 6 + 4) = 10

      j=1:
        Last day: jobs[1...2] = [5, 4]
        maxDifficulty = max(4, 5) = 5
        Previous: dp[1][1] = 6
        dp[3][2] = min(10, 6 + 5) = min(10, 11) = 10

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
FINAL DP TABLE:
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

       day:  0    1    2
    i=0:     0   INF  INF
    i=1:    INF   6   INF
    i=2:    INF   6   11
    i=3:    INF   6   10

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: dp[3][2] = 10 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Optimal partition:
  Day 1: [6, 5] (jobs 0-1) → max = 6
  Day 2: [4] (job 2) → max = 4
  Total: 10

---

📊 Complexity Analysis

Time: O(n² × d)
Space: O(n × d)

---

📊 Approach Comparison

┌────────────────────────────────────────────────────────────────┐
│     MINIMUM DIFFICULTY JOB SCHEDULE - COMPARISON              │
├──────────────────┬──────────┬──────────┬──────────┬────────────┤
│ Approach         │ Time     │ Space    │ Clarity  │ Interview  │
├──────────────────┼──────────┼──────────┼──────────┼────────────┤
│ Recursion        │ O(n^d)   │ O(d)     │ High     │ Start      │
│ Memoization      │ O(n²×d)  │ O(n×d)   │ High     │ Best ✓     │
│ Bottom-Up DP     │ O(n²×d)  │ O(n×d)   │ Medium   │ Good       │
└──────────────────┴──────────┴──────────┴──────────┴────────────┘

For interviews: Show recursion → memoization progression!

---

💻 Complete Working Code

import java.util.Arrays;

public class Solution {
  public int minDifficulty(int[] a, int d) {
    if (a.length < d) {
      return -1;
    }

    // // difficulty for d days.
    // return recursive(a, d, 0);

    // Integer[][] memo = new Integer[a.length + 1][d + 1];
    // return topDown(a, d, 0, memo);

    return bottomUp(a, d);
  }

  private int bottomUp(int[] a, int d) {
    int len = a.length;
    // dp[i][j] => minimum difficulty to complete the FIRST i jobs using j days
    int[][] dp = new int[len + 1][d + 1];
    Arrays.stream(dp).forEach(r -> Arrays.fill(r, Integer.MAX_VALUE));

    // 0 jobs in 0 days => 0 difficulty
    dp[0][0] = 0;

    for (int i = 1; i <= len; i++) {
      for (int day = 1; day <= Math.min(i, d); day++) {
        int maxDifficulty = 0;

        // Try different last day start positions
        // Take jobs [j...i-1] on current day
        for (int j = i - 1; j >= day - 1; j--) {
          maxDifficulty = Math.max(maxDifficulty, a[j]);

          if (dp[j][day - 1] != Integer.MAX_VALUE) {
            dp[i][day] = Math.min(dp[i][day],
                dp[j][day - 1] + maxDifficulty);
          }
        }
      }
    }

    return dp[len][d] == Integer.MAX_VALUE ? -1 : dp[len][d];
  }

  private int topDown(int[] a, int d, int index, Integer[][] memo) {
    if (d == 1) {
      int max = 0;
      for (int i = index; i < a.length; i++) {
        max = Math.max(max, a[i]);
      }

      return max;
    }

    if (memo[index][d] != null) {
      return memo[index][d];
    }

    int res = Integer.MAX_VALUE;
    int currMax = a[index];
    // step 3: why i < a.length - (d - 1)?
    // for [6,5,4,3,2,1] and d = 2
    // i = 0 to 6-(2-1) = 0 to 5
    // for [6,5,4,3,2,1] and d = 3
    // i = 0 to 6-(3-1) = 0 to 4
    // we have 2 keep atleast d jobs for remaining d days.
    for (int i = index; i < a.length - (d - 1); i++) {
      currMax = Math.max(currMax, a[i]);
      // if we see example, we get easily how below example came
      // [6|5,4,3,2,1] => min(6,6+5)
      int remMax = topDown(a, d - 1, i + 1, memo);

      res = Math.min(res, currMax + remMax);
    }

    return memo[index][d] = res;
  }

  private int recursive(int[] a, int d, int index) {
    // step 2: base case (last day)
    // have to finish all remaining jobs
    if (d == 1) {
      int max = 0;
      for (int i = index; i < a.length; i++) {
        max = Math.max(max, a[i]);
      }

      return max;
    }

    // step 1:
    // start from index 0.
    int res = Integer.MAX_VALUE;
    int currMax = a[index];
    // step 3: why i < a.length - (d - 1)?
    // for [6,5,4,3,2,1] and d = 2
    // i = 0 to 6-(2-1) = 0 to 5
    // for [6,5,4,3,2,1] and d = 3
    // i = 0 to 6-(3-1) = 0 to 4
    // we have 2 keep atleast d jobs for remaining d days.
    for (int i = index; i < a.length - (d - 1); i++) {
      currMax = Math.max(currMax, a[i]);
      // if we see example, we get easily how below example came
      // [6|5,4,3,2,1] => min(6,6+5)
      int remMax = recursive(a, d - 1, i + 1);

      res = Math.min(res, currMax + remMax);
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.minDifficulty(new int[] { 6, 5, 4, 3, 2, 1 }, 2) == 7);
    System.out.println(s.minDifficulty(new int[] { 9, 9, 9 }, 4) == -1);
    System.out.println(s.minDifficulty(new int[] { 1, 1, 1 }, 3) == 3);
  }
}

---

🔑 Key Insights

Understanding Loop 3

The inner loop is the HEART of the algorithm!

It answers: "Where should the LAST day start?"

Key points:
  1. Starts at i-1 (last day takes just 1 job)
  2. Ends at day-1 (leave jobs for previous days)
  3. Goes backwards (efficient max computation)
  4. Tries ALL valid partitions

This is what makes DP work! ✓

🎪 Memory Aid

"i = jobs done, day = days used!"
"j = where last day starts!"
"Backwards for efficiency!"
"Leave day-1 jobs for previous days!" ✨

---

📝 Quick Revision Notes

🎯 Loop Summary

for i (1 to n):              // Process i jobs
  for day (1 to min(i,d)):   // Use 'day' days
    for j (i-1 down to day-1): // Last day starts at j
      maxDiff = max(jobs[j...i-1])
      dp[i][day] = min(dp[i][day], dp[j][day-1] + maxDiff)

Complexity: O(n² × d) time, O(n × d) space

---

🎉 Congratulations!

You now understand EVERY loop completely: - ✅ Loop 1: How many jobs (i) - ✅ Loop 2: How many days (day) - ✅ Loop 3: Where last day starts (j) - FULLY EXPLAINED!

The 3rd loop is now crystal clear! 🚀✨