讨论Leetcode问题的一种更好的方法——作业计划的最小难度

Question

您希望在d天内安排作业列表。作业是相关的（即，要处理第i个作业，必须完成所有作业j，其中0<；=j<；i）

你必须每天至少完成一项任务。作业计划的难度是d天中每天的难度总和。一天的难度是当天完成工作的最大难度

给定一个整数数组和一个整数d。第i个作业的难度是作业难度[i]

返回作业计划的最小难度。如果找不到作业的时间表，请返回-1

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

对于上述问题，我有以下解决方案：

from functools import lru_cache
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @lru_cache(None)
        def oneDayDifficulty(start, end):
            if start + 1 == end:
                return jobDifficulty[start]
            mid = (start + end) // 2
            return max(oneDayDifficulty(start, mid), oneDayDifficulty(mid, end))       
        @lru_cache(None)
        def dp(nextTask, days):
            if days == 1:
                return oneDayDifficulty(0, nextTask)
            res = float("inf")
            for startTask in range(days - 1, nextTask):
                res = min(res, dp(startTask, days - 1) + oneDayDifficulty(startTask, nextTask))
            return res
        res = dp(len(jobDifficulty), d)
        return -1 if res == float('inf') else res

我不确定时间和空间的复杂性是什么，它会是O（d*n^2）吗？ 你有更好的办法解决这个问题吗

Answer 1

时间复杂度由รยקคгรђשค

The time complexity is O(dN^2). There are Nd states and work for each state is O(N) at the most.

• 同样的事情，实现起来可能有点简单：

class Solution:
    def minDifficulty(self, nums, d):
        @lru_cache(None)
        def depth_first_search(i, d):
            if d == 1:
                return max(nums[i:])
            res, max_days = float('inf'), 0
            for j in range(i, len(nums) - d + 1):
                max_days = max(max_days, nums[j])
                res = min(res, max_days + depth_first_search(j + 1, d - 1))
            return res

        return -1 if len(nums) < d else depth_first_search(0, d)