<p>You want to schedule a list of jobs in <code>d</code> days. Jobs are dependent (i.e To work on the <code>i<sup>th</sup></code> job, you have to finish all the jobs <code>j</code> where <code>0 &lt;= j &lt; i</code>).</p>

<p>You have to finish <strong>at least</strong> one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the <code>d</code> days. The difficulty of a day is the maximum difficulty of a job done on that day.</p>

<p>You are given an integer array <code>jobDifficulty</code> and an integer <code>d</code>. The difficulty of the <code>i<sup>th</sup></code> job is <code>jobDifficulty[i]</code>.</p>

<p>Return <em>the minimum difficulty of a job schedule</em>. If you cannot find a schedule for the jobs return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/16/untitled.png" style="width: 365px; height: 370px;" />
<pre>
<strong>Input:</strong> jobDifficulty = [6,5,4,3,2,1], d = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> 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 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [9,9,9], d = 4
<strong>Output:</strong> -1
<strong>Explanation:</strong> If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [1,1,1], d = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> The schedule is one job per day. total difficulty will be 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= jobDifficulty.length &lt;= 300</code></li>
	<li><code>0 &lt;= jobDifficulty[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= d &lt;= 10</code></li>
</ul>

class Solution:
    @cache
    def rec_dp(self, start, remaining):
        if remaining == 1:
            return self.max_remaining[start]
        
        res = float("inf")
        day_max = self.jd[start]
        for j in range(start, self.n - remaining + 1):
            day_max = max(day_max, self.jd[j])
            res = min(res, day_max + self.rec_dp(j + 1, remaining - 1))
        return int(res)


    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:

        self.jd = jobDifficulty
        self.n = len(self.jd)
        self.d = d
        if self.n < self.d:
            return -1
        self.max_remaining = [-1 for i in range(self.n)]
        for i in range(self.n - 1, -1, -1):
            if i == self.n - 1:
                self.max_remaining[i] = self.jd[i]
            else:
                self.max_remaining[i] = max(self.jd[i], self.max_remaining[i + 1])
        return self.rec_dp(0, self.d)
# class Solution:
#     def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
#         n = len(jobDifficulty)
#         # Edge case: make sure there is at least one job per day
#         if n < d:
#             return -1

#         # Precompute the maximum job difficulty for remaining jobs
#         max_job_remaining = jobDifficulty[:]
#         for i in range(n - 2, -1, -1):
#             max_job_remaining[i] = max(max_job_remaining[i], max_job_remaining[i + 1])

#         # Use memoization to avoid repeated computation of min_diff states
#         @cache
#         def min_diff(i, days_remaining):
#             # Base case: finish all remaining jobs in the last day
#             if days_remaining == 1:
#                 return max_job_remaining[i]

#             res = float('inf')
#             daily_max_job_diff = 0 # keep track of the maximum difficulty for today

#             # Iterate through possible starting index for the next day
#             # and ensure we have at least one job for each remaining day.
#             for j in range(i, n - days_remaining + 1):
#                 daily_max_job_diff = max(daily_max_job_diff, jobDifficulty[j])
#                 res = min(res, daily_max_job_diff + min_diff(j + 1, days_remaining - 1))

#             return res

#         return min_diff(0, d)

19100