Leetcode 1335:工作计划的最低难度(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1335:工作计划的最低难度(超详细的解法!!!)

in leetcode with 0 comment

你需要制定一份 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 。

示例 4:

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

示例 5:

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

提示:

解题思路

首先比较容易想到递归解法。当jobDifficulty的长度小于d,返回-1。定义函数$f(u,d)$表示区间jobDifficulty[u:]可用天数为d的最优解,那么:

其中$i\in [u,n)$,且$m=max_{k=u}^{i}(jobDifficulty_k)$。

接着考虑边界条件,当d == 0 and u == n的时候,返回0;当d < 0 or u >= n,返回float("inf")

from functools import lru_cache
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        
        @lru_cache(None)
        def dfs(u, d):
            if d == 0 and u == n:
                return 0
            
            if d < 0 or u >= n:
                return float("inf")

            res, m = float("inf"), 0
            for i in range(u, n):
                m = max(m, jobDifficulty[i])
                res = min(res, dfs(i + 1, d - 1) + m)
            return res
        
        return dfs(0, d)

上面的代码中有一个重要的优化,实际上i不用遍历到ni最多遍历到n - d。此时我们需要调整一下边界条件,当d==1的时候,返回max(jobDifficulty[u:])即可。

from functools import lru_cache
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1
        
        @lru_cache(None)
        def dfs(u, t):
            if t == 1:
                return max(jobDifficulty[u:])
            
            res, m = float("inf"), 0
            for i in range(u, n - t + 1):
                m = max(m, jobDifficulty[i])
                res = min(res, dfs(i + 1, t - 1) + m)
            return res
        
        return dfs(0, d)

此时,我们很容易将上面的代码转为递归形式(也就是动态规划)

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

实际上我们不用二维数组,只用一维数组即可。当d=0的时候

而$f(u,d)=min_{i=u}^{n-1}f(i+1,d-1)+m$中的$d$对递推关系没有作用。

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

reference:

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/discuss/490316/JavaC%2B%2BPython-DP

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses