Leecode #1335 工作计划的最低难度

难度：hard

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

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

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

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

示例：

输入：jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
输出：843

输入：jobDifficulty = [7,1,7,1,7,1], d = 3
输出：15

输入：jobDifficulty = [9,9,9], d = 4
输出：-1

解题思路

​ 先看输入的内容，一个数组和一个数。理解一下题目其实就是把长度为l的数组划分为n段，求每一段的最大值的和，我们的目标是让这个和最小。

​ 首先想到用动态规划来做，d(i,j)表示前i天完成前j个任务的最低难度，确定完这个之后我们的算法差不多完成了一半，接下来就是找d(i-1, j-1)和d(i,j)之间的关系了，这就是解题的另外一半了。

​ 首先d这个数组中，有哪些马上确定的量。当i=1时，即只有1天来完成全部的工作，我们可以得到d(1, j)就是这j个任务中的最大值

l = len(jobDifficulty)
d[0][0] = jobDifficulty[0]
for i in range(l):
		d[0][i] = max(jobDifficulty[i], arr[0][i-1])

另外需要注意的是d必须小于或等于任务的数量，因此我们可以确定当d=任务量，最低难度就是全部的工作难度之和，我们在遍历任务长度的时候需要从大于从大于天数的地方开始。

假设, 我们需要确定i天完成j个任务的最低工作难度(此时j>i),

​ d[i-1, j-1] + s[j]，是一个合理的方法，就是用增加的一天完成新增加的任务，但是肯定不是最佳的方法；继续往后遍历 d[i-1, j-2]+max(s[j], s[j-1])也是一个合理的方法，由此我们可以一直遍历到d[i-1,i-1]，然后确定最小的那个工作量，代码如下

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        l = len(jobDifficulty)
        if l < d:
            return -1
        arr = [[100000]*l for i in range(d)]
        arr[0][0] = jobDifficulty[0]
        for i in range(1, l):
            arr[0][i] = max(jobDifficulty[i], arr[0][i-1])
        for i in range(1,d): # 划分为 i 天
            for j in range(i, l): # 前 j 个工作
                pre = jobDifficulty[j] # 记录k-j个工作的最大值
                for k in range(j,i-1,-1): # 注意这里倒序需要i-1
                    pre = max(pre, jobDifficulty[k])
                    arr[i][j] = min(arr[i][j], arr[i-1][k-1] + pre)
        return arr[-1][-1]

运行结果

执行用时 :1016 ms, 在所有 Python3 提交中击败了66.28%的用户

内存消耗 :13.8 MB, 在所有 Python3 提交中击败了100.00%的用户

​