<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:
        n = len(jobDifficulty)
        memo={}

        if d > n:
            return -1

        days = d

        def recurse(i,d):
            nonlocal n,memo,jobDifficulty,days
            #base case 
            if d == 1:
                #take the maximum from the difficulty levels remaining
                return max(jobDifficulty[i:])
            
            #return the result if it is already memoized
            if (i,d) in memo:
                return memo[(i,d)]
            
            #initialize the current Minimum to be infinity
            currMin = float("inf")

            #ensure you keep atleast d jobs for d days
            last = n - d + 2

            #Explore the possibilities
            for idx in range(i+1,last):
                #DFS
                retVal = recurse(idx,d-1)
                #choose the maximum value
                toAdd = max(jobDifficulty[i:idx])
                #calculate the cumulative minimum value
                currMin = min(currMin,retVal+toAdd)

            #memoize the minimum value
            memo[(i,d)] = currMin    
            
            #return the minimum value
            return currMin

        #create the DP table
        dp = [[float("inf")] * (d + 1) for j in range(n)]

        dp[-1][d] = jobDifficulty[-1]
        #initialize the DP table
        for i in range(n-2,-1,-1):
            dp[i][d] = max(dp[i+1][d],jobDifficulty[i])
        
        #iterate and complete the DP table
        for day in range(d-1,0,-1):
            for i in range(day-1,n-(d-day)):
                hardest = 0
                for j in range(i,n-(d-day)):
                    hardest = max(hardest,jobDifficulty[j])
                    dp[i][day] = min(dp[i][day],hardest+dp[j+1][day+1]) 

        return dp[0][1]


        #start the recursion
        res = recurse(0,d)
        #return results
        return res
17000