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

/*
    n is number of jobs

    max jobDifficulty table: mjt[i][j] means max jobDifficulty in range[i , j]

    dp[i][j]: means the minimum difficulty of a job schedule, if we finished 0 to j-th jobs on 0 to i-th day. (j >= i)
    
    dp[i][j] = dp[i-1][j-k] + max one in jobDifficulty [j-k+1, j] (1 <= k <= j-i+1)
             = dp[i-1][j-k] + mjt[j-k+1][j];
    
    pick a k, and try to minimize dp[i][j], takes o(j) time for dp[i][j], worst case O(n)

    total time complexity: O(n^3) -> O(n^2) or O(longn * n^2) ?

    final result: dp[d][n]
*/
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();

        //Max jobDifficulty table: mjt[i][j] means max jobDifficulty in range[i , j]
        vector<vector<int>> mjt(n+1, vector<int>(n+1, 0));
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                mjt[i][j] = max(mjt[i][j-1], jobDifficulty[j-1]);
            }
        }

        //dp[i][j]: means the minimum difficulty of a job schedule, if we finished 0 to j-th jobs on 0 to i-th day. (j >= i)
        vector<vector<int>> dp(d+1, vector<int>(n+1, 0));
        for(int j = 1; j<=n; j++){
            dp[0][j] = mjt[1][j];
        }
        dp[d][n] = -1;

        for(int i = 1; i <= d; i++){
            for(int j = i; j <= n; j++){//j = 2
                int minJobDifficultyToday = INT_MAX;
                for(int k = 1; k <= j-i+1; k++){//k = 1, 2
                    minJobDifficultyToday = min(minJobDifficultyToday, dp[i-1][j-k] + mjt[j-k+1][j]);//dp[0][1]+mjt[2][2], dp[0][0]+mjt[1][2]
                }
                dp[i][j] = minJobDifficultyToday;
            }
        }

        return dp[d][n];

    }
};
15900