1335 工作计划的最低难度(动态规划)
发布日期:2021-05-07 21:56:23 浏览次数:25 分类:精选文章

本文共 1380 字,大约阅读时间需要 4 分钟。

为了解决这个问题,我们需要制定一个d天的工作计划,每天至少完成一项任务,并且工作之间存在依赖关系。我们的目标是找到整个计划的最小总难度,如果无法完成任务则返回-1。

方法思路

我们可以使用动态规划来解决这个问题。定义一个二维数组dp,其中dp[i][j]表示在第i天完成j项工作的最小总难度。我们需要填充这个二维数组,找到最优的工作安排方式。

  • 初始化:dp[1][1]表示第一天完成第一项任务的难度。
  • 填充第一天:第一天完成1到n项任务的难度,取每一天的最大任务难度。
  • 动态规划递推:对于每一天i,考虑前一天完成k项工作的情况,计算当前天完成j - k项工作的最小总难度。逆序遍历k,确保考虑所有可能的前一天任务数。
  • 结果检查:如果dp[d][n]未被赋值,说明无法完成任务,返回-1。
  • 解决代码

    from typing import Listclass Solution:    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:        n = len(jobDifficulty)        if n < d:            return -1                dp = [[-1] * (n + 1) for _ in range(d + 1)]        dp[1][1] = jobDifficulty[0]        for i in range(2, n + 1):            dp[1][i] = max(dp[1][i - 1], jobDifficulty[i - 1])                for i in range(2, d + 1):            for j in range(i, n + 1):                dp[i][j] = dp[i - 1][j - 1] + jobDifficulty[j - 1]                for k in range(j - 2, i - 2, -1):                    current_max = max(jobDifficulty[k], jobDifficulty[j - 1])                    if dp[i - 1][k] + current_max < dp[i][j]:                        dp[i][j] = dp[i - 1][k] + current_max                return dp[d][n] if dp[d][n] != -1 else -1

    代码解释

  • 初始化:检查任务数是否超过天数,初始化dp数组,dp[1][1]设为第一项任务的难度。
  • 填充第一天:计算第一天完成1到n项任务的最大难度。
  • 动态规划递推:对于每一天i,计算每一天完成j项任务的最小总难度,考虑前一天完成k项任务的情况,逆序遍历k以确保所有可能情况被考虑。
  • 结果检查:返回dp[d][n],如果未被赋值则返回-1。
  • 通过这种方法,我们可以高效地找到完成任务的最小总难度,确保每天至少完成一项任务并满足依赖关系。

    上一篇:python标准库--heapq堆队列算法
    下一篇:1009 十进制整数的反码(模拟)

    发表评论

    最新留言

    能坚持,总会有不一样的收获!
    [***.219.124.196]2025年04月24日 10时50分59秒