1335 minimum difficulty of a job schedule

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/

一共两个地方用到了dp，第一个是你要知道任意一端区间内的difficulty最大值是多少，第二是求minimum difficulty的时候，注意在第i天至少应该做完了第i项任务，同时每天至少要做一个任务

因此dp的思路就是在第i天假设前i-1天做了k项任务(k至少为i-1)，剩下的在第i天做，遍历所有k找到最小值即可

class Solution {
    public int minDifficulty(int[] diff, int d) {
        if (diff.length < d) return -1;
        int n = diff.length;
        // dp[i][j] is min total diff until the ith day if arrange jobs from 0 - j
        int[][] dp = new int[d][n];
        dp[0][0] = diff[0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = Math.max(dp[0][i - 1], diff[i]);
        }
        int[][] maxdiff = new int[n][n];
        for (int i = 0; i < n; i++) {
            maxdiff[i][i] = diff[i];
        }
        for (int i = 0; i < n; i++) {
            for (int len = 1; i + len < n; len++) {
                int j = i + len;
                maxdiff[i][j] = Math.max(maxdiff[i][j - 1], diff[j]);
            }
        }
        for (int i = 1; i < d; i++) {
            for (int j = i; j < n; j++) {
                int profit = Integer.MAX_VALUE;
                for (int k = i - 1; k < j; k++) {
                    profit = Math.min(profit, dp[i - 1][k] + maxdiff[k + 1][j]);
                }
                dp[i][j] = profit;
            }
        }
        return dp[d - 1][n - 1];
    }
}