Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

1335. Minimum Difficulty of a Job Schedule

給你很多要照順序執行的 jobs 的困難度和天數 d  問你怎麼執行總困難度最低

當天困難度=當天執行的 jobs 中困難的最大值

Example:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7

第一天執行[6,5,4,3,2], max=6, 第二天執行[1], max=1

總困難度7

如果第一天執行[6] 第二天執行[5,4,3,2,1] 總困難度是6+5=11


思路:

1.其實和昨天的題目有點像 都是要把一個 array 分成 d 塊

dp[j][d-1] = min(dp[j][d-1], dp[i][d] + jobs[i:j]增加的cost)

dp[i][d] 代表 jobs[0:i]已經分好了並且後面還剩 d 刀能切


2.jobs[i:j]增加的cost 就是 jobDifficulty[i:j] 的最大值

更新的步驟跟昨天的很像 不過維護最大值簡單很多


3.題目要求每天都要有工作 所以最後的 d 要是 0

也就是 return dp[n][0]


Python code:

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        dp = [[float('inf')]*(d+1) for _ in range(n+1)]
        dp[0][d] = 0

        for i in range(n):
            for j in range(1, d+1):

                maxjob = jobDifficulty[i]
                for k in range(i, n):
                    maxjob = max(maxjob, jobDifficulty[k])
                    dp[k+1][j-1] = min(dp[k+1][j-1], dp[i][j] + maxjob)

        return dp[n][0] if dp[n][0] != float('inf') else -1

時間複雜度O(nnd)



4.lee215提供了一個 O(nd) 的解法 非常精彩

    def minDifficulty(self, A, d):
        n = len(A)
        if n < d: return -1
        dp, dp2 = [float('inf')] * n, [0] * n
        for d in xrange(d):
            stack = []
            for i in xrange(d, n):
                dp2[i] = dp[i - 1] + A[i] if i else A[i]
                while stack and A[stack[-1]] <= A[i]:
                    j = stack.pop()
                    dp2[i] = min(dp2[i], dp2[j] - A[j] + A[i])
                if stack:
                    dp2[i] = min(dp2[i], dp2[stack[-1]])
                stack.append(i)
            dp, dp2 = dp2, dp
        return dp[-1]


用 stack 優化了計算區間最大值並且更新答案的部分

每次都讓 dp 多切一個區間 切了 d 次以後 dp[-1] 就是答案

iterate dp 時維護一個嚴格遞減的 stack

只要 top 比自己小就嘗試用他來更新自己的答案

先看code

dp2[i] = min(dp2[i], dp2[j] - A[j] + A[i])  #j<i

這行 dp2[j] 也是剛切完的 來自dp2[j-1] + A[j] (*或是其他包含A[j]的切法)

所以如果 A[i] >= A[j] 就可以嘗試用 dp2[j] - A[j] + A[i] 來更新自己

因為 dp2[j] 這階段切的最大值就是 A[j] (*真的嗎?) 所以才能直接用 A[i] 取代

最後如果 stack top 比你大 也就是 A[j] > A[i], j < i

那就代表多切進 A[i] 不會影響最大值 那也就嘗試更新看看

也就是 dp2[i] = min(dp2[i], dp2[stack[-1]])


*: dp2[j] 這回合有可能被誰更新?
1. dp[j-1] + A[j] 就是上一輪的 j-1 多切一個
2. 比自己小的 stack top  也就是這輪先做完的其他人 這種情況下就會包含到 A[j]
3. 比自己大的 stack top  叫他 k 好了 這樣 dp2[j] = min(dp2[j], dp2[k])
如果 A[k] 也比 A[i] 大 那等等 dp2[k] 還是能更新到 dp2[i]
並且剛剛計算的 dp2[j] - A[j] + A[i] 會大於 dp2[k] (因為A[j] < A[i])
所以不用擔心更新到錯誤答案
如果 A[k] 比 A[i] 小 那一樣 dp2[j] - A[j] + A[i] > dp2[j] - A[k] + A[i]
dp2[j] - A[j] + A[i] 是不是對的也不重要了 因為等等會被 k 蓋掉
至於 dp2[j] - A[k] + A[i] 這個答案是不是對的? 那就要再問一次
dp2[k]這回合有可能被誰更新?


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.214.153 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665908702.A.190.html
推 Rushia: hard大師
推 JerryChungYC: 大師
→ unclerock: 大師
→ twosheep0603: 好典型的DP
※ 編輯: pandix (111.251.214.153 臺灣), 10/17/2022 00:11:39
推 NTHUlagka: 大神 講的超好的欸
推 GTR12534: 一開始連題目都看不懂 不知道怎麼下手 G_G