1335. 工作计划的最低难度

你在事业上碰到挫折，有打退堂鼓的动机时，你就应加以留意，这是最危险的时候!——乔布斯。

参考1335. 工作计划的最低难度，难度分2035。

题目

你需要制定一份 d 天的工作计划表。工作之间存在依赖，要想执行第 i 项工作，你必须完成全部 j 项工作（ 0 <= j < i）。

你每天 至少 需要完成一项任务。工作计划的总难度是这 d 天每一天的难度之和，而一天的工作难度是当天应该完成工作的最大难度。

给你一个整数数组 jobDifficulty 和一个整数 d，分别代表工作难度和需要计划的天数。第 i 项工作的难度是 jobDifficulty[i]。

返回整个工作计划的 最小难度 。如果无法制定工作计划，则返回 -1 。

jobDifficulty = [6,5,4,3,2,1], d = 2

输入：jobDifficulty = [6,5,4,3,2,1], d = 2
输出：7
解释：第一天，您可以完成前 5 项工作，总难度 = 6.
第二天，您可以完成最后一项工作，总难度 = 1.
计划表的难度 = 6 + 1 = 7 
输入：jobDifficulty = [9,9,9], d = 4
输出：-1
解释：就算你每天完成一项工作，仍然有一天是空闲的，你无法制定一份能够满足既定工作时间的计划表。
输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：工作计划为每天一项工作，总难度为 3 。

解题思路

• 记忆化搜索：考虑递归搜索dfs(n,d),问题转化为求子问题dfs(i,j),表示i项工作花费j天完成。

记忆化搜索

class Solution {

    int[] jobs;
    int[][] memo;
    public int minDifficulty(int[] jobDifficulty, int d) {
        //题意:1.必须按顺序完成前面的工作才能做后面的工作
        //2.每天的工作数量>=1 难度为最大的那个 必须安排d天
        jobs = jobDifficulty;
        if(jobs.length < d) return -1;
        //考虑递归记忆化搜索(选或不选)
        memo = new int[jobs.length+1][d+1];
        for(int i = 0; i < memo.length; i++) Arrays.fill(memo[i],-1);
        return dfs(jobs.length,d);
    }

    //完成i项工作话费j天的最小工作难度
    int dfs(int i,int j) {
        if(memo[i][j] != -1) return memo[i][j];
        if(j == 1) { //此时最小工作难度即为全部i项工作的最大难度
            int max = 0;
            for(int k = 0; k < i; k ++)max = Math.max(max,jobs[k]);
            return memo[i][j] = max;
        }
        //枚举前j-1天完成的工作项数目范围为j-1,i-1
        int min = Integer.MAX_VALUE,max = 0;
        for(int k = i-1; k >= j-1; k--) { //倒序计算可以防止重复进行区间最大难度的计算
            //j-1天完成k项则j天完成的工作项下标范围为k,i-1倒序为i-1,k
            max = Math.max(max,jobs[k]);
            min = Math.min(min,dfs(k,j-1)+max);
        }
        return memo[i][j] = min;
    }
}

复杂度分析

• 时间复杂度：O(dn^2)，记忆化搜索状态个数为dn,单个状态搜索时间为n,n为工作数量。
• 空间复杂度：O(dn)，即记忆数组空间dn。