<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:
    
    struct Key{
        int job;
        int day;
        
        Key(int j,int d):job(j),day(d) {}
        
        bool operator==(const Key& other) const{
            return job==other.job && day==other.day;
        }
    };
    
    struct KeyHash{
        size_t operator()(const Key& k) const{
            return std::hash<int>()(k.job) ^ (std::hash<int>()(k.day) << 1);  
        }
    };
    
    
    unordered_map<Key,int,KeyHash> memo;
    
    vector<int> jobDifficulty;
    int d;    
    int* hardestToEnd;
    
    void hardest(){ 
        int nJobs=jobDifficulty.size();
        hardestToEnd= new int[nJobs];
        hardestToEnd[nJobs-1]=jobDifficulty[nJobs-1];
        for (int i=nJobs-2;i>=0;--i){
            hardestToEnd[i]=max(jobDifficulty[i],hardestToEnd[i+1]);
        }
    }

    
    int dp(int day, int j){
        if (day==d){
            return (hardestToEnd[j]);
        }
        
        Key k(day,j);
        if (memo.find(k)!=memo.end())
            return memo[k];
                        
        int nj=jobDifficulty.size();
        int best=hardestToEnd[0]*d;
        
        for (int job=j;job<nj-(d-day);++job){
            //find hardest job from j to i
            int difficultyOfDay=jobDifficulty[j];
            for (int i=j+1;i<=job;++i){
                difficultyOfDay=max(difficultyOfDay, jobDifficulty[i]);
            }
            best=min(dp(day+1,job+1)+difficultyOfDay,best);
        }
                        
        memo[Key(day,j)]=best;                
        return best;
    }
    
    
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        this->d=d;
        this-> jobDifficulty=jobDifficulty;
        hardest();
        
        if (jobDifficulty.size()<d){
            return -1;
        }
        
        return dp(1,0);
    }
};
13000