<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>

#define LL long long
#define PQ priority_queue
#define VI vector<int>
#define VL vector<long>
#define VUL vector<unsigned long>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VVL vector<vector<long>>
#define VVUL vector<vector<unsigned long>>
#define VVB vector<vector<bool>>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VS vector<string>
#define VSEI vector<set<int>>
#define VVS vector<vector<string>>
#define PII pair<int, int>
#define PLL pair<long, long>
#define PLI pair<long, int>
#define VPII vector<pair<int, int>>
#define VPLL vector<pair<long, long>>
#define VVPII vector<vector<pair<int, int>>>
#define VVPLL vector<vector<pair<long, long>>>
#define VVPLI vector<vector<pair<long, int>>>
#define UMII unordered_map<int, int>
#define UMSS unordered_map<string, string>
#define UMCS unordered_map<char, string>
#define UM unordered_map
#define USI unordered_set<int>
#define USS unordered_set<string>
#define QPII queue<pair<int, int>>

#define DSZ(g, M, N) const int M = g.size(), N = g[0].size()
#define D4(dx, dy)             \
    int dx[4] = {-1, 1, 0, 0}; \
    int dy[4] = {0, 0, -1, 1}
#define D8(dx, dy)                           \
    int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; \
    int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}
#define OB(x, y, M, N) ((x) >= (M) || (y) >= (N) || (x) < 0 || (y) < 0)
using AI3 = std::array<int, 3>;
using VAI3 = std::vector<std::array<int, 3>>;
using AI4 = std::array<int, 4>;
using VAI4 = std::vector<std::array<int, 4>>;

#define G_DSZ(g, M, N) const int M = g.size(), N = g[0].size()
#define G_D4D(d) vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
#define G_D8D(d) vector<pair<int, int>> d = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}
#define G_SZ(g, M, N) M = g.size(), N = g[0].size()
#define G_OB(x, y, M, N) ((x) >= (M) || (y) >= (N) || (x) < 0 || (y) < 0)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
class Solution {
public:
    int minDifficulty(vector<int>& jobs, int d) {
        const int n = jobs.size();
        if (n < d) return -1;
        // solve: dp(n,d),
        // dp(i,k): min difficulty of schedule of first i jobs into k days
        // difficulty of schedule: sum of difficulties on each day
        // (that day's maxi difficult job)
        VVI dp(n + 1, VI(d + 1, INT_MAX));
        int maxiSoFar = jobs[0];
        FOR(i, 1, n) {
            maxiSoFar = max(maxiSoFar, jobs[i - 1]);
            FOR(k, 1, d) {
                if (k == 1) {
                    dp[i][1] = maxiSoFar;
                } else {
                    // for every j : let j be the index of first job in the last group
                    // j<=i-1 && j >=k-1
                    FOR(j, k - 1, i - 1) {
                        // last day jobs: nums[j]...nums[i-1]
                        int maxiLastDay = *max_element(jobs.begin() + j, jobs.begin() + i);
                        dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxiLastDay);
                    }
                }
            }
        }
        return dp[n][d] == INT_MAX ? -1 : dp[n][d];
    }
};

9900