[
array
dp
monotonic deque
]
BinarySearch 0812 Job Scheduling to Minimize Difficulty
Problem statement
https://binarysearch.com/problems/Job-Scheduling-to-Minimize-Difficulty/
Solution
Equal to Leetcode 1335. Minimum Difficulty of a Job Schedule.
Complexity
Time is O(nk^2)
, space is O(nk)
Code
class Solution:
def solve(self, A, k):
@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), k)) != float("inf") else -1
Remark
There is O(nk)
time complexity solution, using monotonic deque technique.