<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:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        """
        1. Subproblem: given a job, what is the minimum difficulty if I take it today.
        2. find_min_difficulty:
            - Given a specific # of remaining days, iterate through all possible jobs I can take while ensuring 
              enough days are available to complete the remaining jobs (len(jobDifficulty) - days_remaining + 1):
                - If you take the job, find the max job within this timeframe (to get max difficulty of current 
                  day) and increment it by the min difficulty that can be achieved if we take the next job with 
                  1 less day remaining (to ensure i > j).
            - Base case: if only one day is remaining, return the max jobDifficulty of the jobs remaining (since
              we must do all the remaining jobs).
        3. Leverage memoization to avoid duplicate work of finding the min difficulty with a certain # of days 
           remaining and at a certain job.
        """
        memo = {}
        n = len(jobDifficulty)
        if n < d:
            return -1

        def find_min_diff(job, days_remaining):
            if days_remaining == 1:
                return max(jobDifficulty[job:])
            if (job, days_remaining) not in memo:
                max_day_diff, min_diff = 0, math.inf
                for i in range(job, n - days_remaining + 1):
                    max_day_diff = max(max_day_diff, jobDifficulty[i])
                    min_diff = min(min_diff, max_day_diff + find_min_diff(i+1, days_remaining-1))
                memo[(job, days_remaining)] = min_diff
            return memo[(job, days_remaining)]
        
        return find_min_diff(0, d)
17500