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.