Leetcode 1335. Minimum Difficulty of a Job Schedule

Problem statement

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/

Solution 1

The question is to separate our list into d parts, such that sum of maximum among lists is minimal. The idea is to use dp with states (i, k) where we need to split numbers [0, ..., i-1] into k parts.

1. If we have number of parts equal to number of numbers, we return sum of them.
2. If we have number of numbers less than parts or zero parts (but not zero numbers, we checked this already), return plus infinity.
3. Then we go by j from i-1-th number upto k-1 inclusive and look at dp(j, k-1) + maximum on range. We can suppurt cumulative maximum.

Complexity

Time complexity is O(n*n*d), because we have O(nd) states and O(n) transactions from one state to others. Space complexity is O(nd)

Code

class Solution:
    def minDifficulty(self, A, d):
        @lru_cache(None)
        def dp(i, k):
            if i == k: return sum(A[:i])
            if i < k or k == 0: return float("inf") 
            T, ans = -float("inf"), float("inf")

            for j in range(i-1, k-2, -1):
                T = max(T, A[j])
                ans = min(ans, dp(j, k-1) + T)
            return ans
        
        return ans if (ans := dp(len(A), d)) != float("inf") else -1

Solution 2

There is better solution with O(nd) complexity, using idea of monotonic stack.

Complexity

It is O(nd) for time and space is O(n).

Code

# code is borrowed from Lee215
class Solution:
    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]