Hard

题目描述

你需要在 d 天内完成一系列工作。工作是有依赖关系的（即要完成第 i 个工作，你必须完成所有 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
解释：即使你每天完成一个工作，仍然有一天是空闲的。你无法为给定的工作安排计划。

示例 3：

输入：jobDifficulty = [1,1,1], d = 3
输出：3
解释：计划是每天一个工作。总难度为 3。

提示：

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

解题思路

这是一道典型的动态规划问题，需要将工作数组分割成 d 个连续的子数组。

思路分析：

首先，如果工作数量少于天数，显然无法安排计划，返回 -1。

我们使用二维动态规划来解决：

  • dp[i][j] 表示前 i 个工作在 j 天内完成的最小难度
  • 状态转移：对于第 j 天，我们需要决定这一天完成哪些工作

具体来说，对于 dp[i][j]，我们枚举第 j 天开始的位置 k，那么：

  • 前 k 个工作用 j-1 天完成，难度为 dp[k][j-1]
  • 第 k+1 到第 i 个工作在第 j 天完成，难度为这些工作中的最大值

优化思路：

  1. 可以预处理区间最大值来优化查询
  2. 使用滚动数组优化空间复杂度
  3. 从右到左更新可以使用一维数组

推荐使用一维数组从右到左更新的方法，既节省空间又保证正确性。

边界条件：

  • 第一天的状态：dp[i][1] 等于前 i 个工作的最大值
  • 无法完成的情况：工作数小于天数

代码实现

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        if (n < d) return -1;
        
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int day = 1; day <= d; day++) {
            for (int i = n; i >= day; i--) {
                dp[i] = INT_MAX;
                int maxDiff = 0;
                for (int j = i; j >= day; j--) {
                    maxDiff = max(maxDiff, jobDifficulty[j - 1]);
                    if (dp[j - 1] != INT_MAX) {
                        dp[i] = min(dp[i], dp[j - 1] + maxDiff);
                    }
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for day in range(1, d + 1):
            for i in range(n, day - 1, -1):
                dp[i] = float('inf')
                max_diff = 0
                for j in range(i, day - 1, -1):
                    max_diff = max(max_diff, jobDifficulty[j - 1])
                    if dp[j - 1] != float('inf'):
                        dp[i] = min(dp[i], dp[j - 1] + max_diff)
        
        return dp[n]

public class Solution {
    public int MinDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.Length;
        if (n < d) return -1;
        
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int day = 1; day <= d; day++) {
            for (int i = n; i >= day; i--) {
                dp[i] = int.MaxValue;
                int maxDiff = 0;
                for (int j = i; j >= day; j--) {
                    maxDiff = Math.Max(maxDiff, jobDifficulty[j - 1]);
                    if (dp[j - 1] != int.MaxValue) {
                        dp[i] = Math.Min(dp[i], dp[j - 1] + maxDiff);
                    }
                }
            }
        }
        
        return dp[n];
    }
}

var minDifficulty = function(jobDifficulty, d) {
    const n = jobDifficulty.length;
    if (n < d) return -1;
    
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let day = 1; day <= d; day++) {
        for (let i = n; i >= day; i--) {
            dp[i] = Infinity;
            let maxDiff = 0;
            for (let j = i; j >= day; j--) {
                maxDiff = Math.max(maxDiff, jobDifficulty[j - 1]);
                if (dp[j - 1] !== Infinity) {
                    dp[i] = Math.min(dp[i], dp[j - 1] + maxDiff);
                }
            }
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²d)n 是工作数量，d 是天数，三重循环
空间复杂度O(n)使用一维数组存储状态