<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 {
private:
    long long getMinDifficulty(vector<int>&a,int ind,int d,int n,vector<vector<long long>>&dp){

        if(ind>n || d==0) return INT_MAX;
        if(ind==n){
            return d==1 ? 0 : INT_MAX;
        }
        if(dp[ind][d]!=-1) return dp[ind][d];

        long long minDiff = INT_MAX;
        long long curMax = INT_MIN;

        for(int i=ind; i<n; i++){
            curMax = max(curMax , (long long)a[i]);
            //if(i==n-1) return d==1 ? curMax : INT_MAX;
            minDiff = min(minDiff , curMax+getMinDifficulty(a,i+1,d-1,n,dp));
        }
        return dp[ind][d] = minDiff;
        
    }
    long long getMinDifficultyTab(vector<int>&a,int d,int n){

        vector<vector<long long>>dp(n+1,vector<long long>(d+1,0));

        for(int i=1; i<=d; i++) dp[n][i] = INT_MAX;

        for(int i=n-1; i>=0; i--){
            for(int j=d; j>=0; j--){

                long long minDiff = INT_MAX;
                long long curMax = INT_MIN;

                for(int k=i; k<n; k++){
                    curMax = max(curMax , (long long)(a[k]));
                    minDiff = min(minDiff , j-1<0 | i+1>n ? INT_MAX : curMax+dp[k+1][j]);
                }
                dp[i][j]=minDiff;
            }
        }
        return dp[0][d];
    }
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        
        int n = jobDifficulty.size();
        if(d>n) return -1;
        //return getMinDifficultyTab(jobDifficulty,d,n);
        vector<vector<long long>>dp(n+1,vector<long long>(d+2,-1));
        return getMinDifficulty(jobDifficulty,0,d+1,n,dp);
    }
};
10300