LeetCode1335. 工作计划的最低难度（第173场周赛）

题目描述

没参加比赛，我喜欢比赛过后再来做嘿嘿，思维比较慢，可以慢慢想，比不过大神们QAQ，不过这道题个人认为比较简单，可以算中等题。

你必须完成全部 j 项工作（ 0 <= j < i）。
你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。
给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。
返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

示例1

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7

示例2

输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。

思路

直接上代码，不多BB

下面直接上代码：

class Solution {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int len=jobDifficulty.length;
        if(len<d)return -1;
        if(len==d){
            int res=0;
            for(int i=0;i<len;i++){
                res+=jobDifficulty[i];
            }
            return res;
        }

        int [][]dp=new int [len][d+1];
        dp[0][1]=jobDifficulty[0];
        for(int j=2;j<=d;j++){
            dp[0][j]=-1;
        }
        int max=jobDifficulty[0];
        for(int i=0;i<len;i++){
            if(jobDifficulty[i]>max)max=jobDifficulty[i];
            dp[i][1]=max;
        }

        if(d==1)return max;
        int maxRes;
        for(int i=1;i<len;i++){
            for(int j=2;j<=d;j++){

                max=jobDifficulty[i];
                
                dp[i][j]=Integer.MAX_VALUE;
                for(int k=i;k>=1;k--){
                    max=Math.max(max,jobDifficulty[k]);
                    if(dp[k-1][j-1]!=-1) 
                    dp[i][j]=Math.min(dp[i][j],max+dp[k-1][j-1]);
                    
                }
                if(dp[i][j]==Integer.MAX_VALUE)dp[i][j]=-1;
            }
        }

        return dp[len-1][d];
    }
}

运行时间：

最后唠嗑几句，我太爱动态规划了！！！！！！