<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 {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        // find a d partition of the jobDifficulty array to minimize the sum of the max of each subarray
        vector<int>& jd = jobDifficulty;
        int N = jd.size();
        if(N<d)
            return -1;
        vector<vector<map<int, int>>> res(N, vector<map<int,int>>(d+1));
        res[0][1][jd[0]] = jd[0];
        for(int i=1; i<N; ++i) {
            //jd[i]  attach to existing subarray:
            for(int k=1; k<=d; ++k) {
                for(auto [x, y]: res[i-1][k]) {
                    if(x < jd[i]) {
                        auto it = res[i][k].find(jd[i]);
                        if(it == res[i][k].end())
                            res[i][k][jd[i]] = res[i-1][k][x] + (jd[i] - x);
                        else
                            it->second = min(it->second, res[i-1][k][x] + (jd[i] - x));
                    }
                    else {
                        res[i][k][x] = y;
                    }
                }
            }
            for(int k=2; k<=d; ++k) { // starting a new subarray:
                int mini = INT_MAX;
                for(auto [z,w]: res[i-1][k-1]) {
                    mini = min(w, mini);
                }
                if(mini != INT_MAX) {
                    auto it = res[i][k].find(jd[i]);
                
                    if(it == res[i][k].end()) {
                        res[i][k][jd[i]] = mini + jd[i];
                    }
                
                    else {
                    
                        it->second = min(it->second, mini+jd[i]);
                
                    }
                }
            
            }
        }
        #if 0
        for(int i=0; i<N; ++i) {
            cout << "i= " << i << "---- ";
            for(int j=1; j<=d; ++j) {
                for(auto [x,y]: res[i][j])
                    cout << x <<"," <<j<<" ";
            }
            cout << "\n";
        }
        #endif 
        int ans = INT_MAX;
        for(auto [x,y]: res[N-1][d]) {
            ans = min(y, ans);
        }
        return ans;
    }
};
21000