讨论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

我们可以有O(d * n * log n)。让dp[i][d]代表分配给第d天的第i个任务的最佳选择。然后：

dp[i][d] ->
  min (
    max(A[j..i]) + dp[j-1][d-1]
  ) for d - 1 ≤ j ≤ i

我们可以将迄今为止看到的所有dp[j][d]存储在按A[j]排序的二叉搜索树中，并添加了与左子树中的任何节点关联的最小dp[j-1][d-1]和与右子树中的任何节点关联的A[j] + dp[j-1][d-1]的修饰；与它配对的j一起。当我们到达A[i]时，我们查找它在树中的位置，跟踪与高于它的任何节点关联的最小A[j] + dp[j-1][d-1]，以及与等于或低于它的任何节点关联的最小dp[j-1][d-1]。那么我们的选择就变成了：

dp[i][d] ->
  min (
    // A[i] is the first value on day d
    A[i] + dp[i-1][d-1],
    // A[i] would not affect this one
    A[j_higher] + dp[j_higher-1][d-1],
    // A[i] becomes the max for this one
    A[i] + dp[j_eq_or_lower-1][d-1]
  )
  where j_higher is the one paired with the minimum A[j] + dp[j-1][d-1]
  associated with a higher A[j], and j_eq_or_lower is the one paired
  with the minimum dp[j-1][d-1] associated with a lower or equal A[j]

在O(log n)中插入、更新装饰并在树中查找，我们对每个d执行O(n)次

Answer 2

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

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)

Answer 3

我们可以在O(d*N)时间复杂度中使用O(N)空间，使用堆栈

说明：

dp配方：

这个公式与here几乎没有什么不同。因为我们可以使用堆栈计算到目前为止在当天d发现的最大难度的成本

dp[i][d] -  represent minimum difficulty that can be achieved considering d days and first i jobs.

重复性：

有3种情况：

1. ith作业是d天的唯一作业，其余所有作业在{}天之前完成
2. 我们尝试添加到当前日期，并查看A[i]是否比当前已完成的任何先前更高难度的工作j难度更大d
3. 有一项难度更高的工作j我们在今天前面看到的d

---

dp[i][d] = min( A[i] + dp[i-1][d-1], // ith job is the only job on day d 
                A[i] + (dp[j][d] - A[j]), // or we try adding to current day and see if A[i] has more difficulty than any previous higher difficulty job j already completed on present day
                dp[j][d] // or there is some higher difficulty job `j` we saw previously on present day `d`.
              )

C++实现：

我们维护堆栈以计算迄今为止所看到的最高难度作业j。正如我们在递归中看到的，我们只需要前一天的值来计算当天的值，所以我们在那里节省了空间

int minDifficulty(vector<int>& A, int D) {
    int jobs = A.size();
    if (jobs < D) return INT_MAX ; // impossible to do atleast 1 job everyday
    int max_difficulty = *max_element(A.begin(), A.end()) + 1;
    vector<int> prv_day(jobs, max_difficulty), curr_day(jobs);
    for (int days = 0; days < D; ++days) {
        vector<int> stack;
        for (int i = days; i < jobs; i++) {
            curr_day[i] = i > 0 ? prv_day[i - 1] + A[i] : A[i]; // start fresh day with first job as ith
            while (!stack.empty() && A[stack.back()] <= A[i]) {
                int j = stack.back(); stack.pop_back();
                curr_day[i] = min(curr_day[i], curr_day[j] - A[j] + A[i]); // or we try extending and see if A[i] has more difficulty than any previous job j on present day 
            }
            if (!stack.empty()) {
                curr_day[i] = min(curr_day[i], curr_day[stack.back()]); // or there is some higher difficulty job we saw previously
            }
            stack.push_back(i);
        }
        swap(prv_day, curr_day);
    }
    return prv_day[jobs - 1];
}

时间复杂性：

对于每一天，我们都要花费O(N)时间来计算。所以时间复杂度是O(d*N)。堆栈中的项最多被推送和弹出O(N)次

额外空间复杂性：

O(N)存储当前和以前的状态，以及O(N)存储堆栈