1335. 工作计划的最低难度

原题地址：https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/

题解

二维动态规划

这道题的含义是：给定一个数组，将其切分成多个连续的子区间，求每个子区间最大值之和的最小值

设dp[i][j]为第i天完成了第j项，我们知道第i天肯定是完成了一个子区间内的任务，如果第i-1天完成的任务为第k项，那么第i天完成的任务子区间就是[k+1,j]，则我们知道：

为了方便遍历，我们将k设为子区间的第一个值，即第i天完成的第一项任务，这样，第i-1天完成的任务就变成了第k-1项，此时dp方程变为：

另k遍历[0,j]，求所有情况下的最小值即为dp[i][j]的值

考虑几种特殊情况：

• 由于每天必须完成一项任务，我们不能将第1项任务拖到第2天才做
  • 当j<i时，dp[i][j]直接等于-1
• 由于剩余天数每天也必须完成一项任务，我们不能一次性完成太多任务导致剩余天数无事可做
  • 当jobDifficulty.length-j<d-i时，dp[i][j]直接等于-1
• i=0和j=0情况下的边界条件也可以通过上面两项设置
• 当dp[i-1][k-1]为-1时，说明k在这种情况下不可行，需要直接跳过该情况

最终输出dp[d-1][jobDifficulty.length-1]即可，当该值不正常（如小于0等）时则输出-1

时间复杂度：

空间复杂度：

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int[][] dp=new int[d][jobDifficulty.length];
        int max,ans=Integer.MAX_VALUE;
        max=Integer.MIN_VALUE;

        //第0天一次性完成j项工作
        for(int j=0;j<jobDifficulty.length;j++){
            //当一次性工作太多，无法满足剩余天数需求时等于-1
            if(jobDifficulty.length-j-1<d-0-1){
                dp[0][j]=-1;
            }else{
                max=Math.max(max,jobDifficulty[j]);
                dp[0][j]=max;
            }
        }

        //第i天才完成第0项工作
        for(int i=0;i<d;i++){
            if(i==0)dp[i][0]=jobDifficulty[0];
            //由于每天必须完成一项工作，除第0天完成第0项工作外其余全等于-1
            else dp[i][0]=-1;
        }

        for(int i=1;i<d;i++){
            for(int j=1;j<jobDifficulty.length;j++){
                //每天必须完成一个任务：j<i
                //剩余任务数必须满足剩余天数需要：jobDifficulty.length-j<d-i
                if(j<i||jobDifficulty.length-j<d-i){
                    dp[i][j]=-1;
                }else{
                    dp[i][j]=Integer.MAX_VALUE;
                    max=Integer.MIN_VALUE;
                    for(int k=j;k>=1;k--){
                        max=Math.max(max,jobDifficulty[k]);
                        if(dp[i-1][k-1]!=-1){
                            dp[i][j]=Math.min(dp[i][j],dp[i-1][k-1]+max);
                        }
                    }
                }
            }
        }
        return dp[d-1][jobDifficulty.length-1]<0?-1:dp[d-1][jobDifficulty.length-1];
    }
}