Leetcode # 1335. Minimum Difficulty of a Job Schedule

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

Solution: Top-Down DP

n := len(jobDifficulty)

Time Complexity: O((d * n) * n) = O(d * (n ** 2))
recursion call stack: O(d * n)
for i in range(start, n): … min_difiiculty(i + 1, _d – 1)…
calculating min_difiiculty(): O(len ** 2)O(n)
min([(max( … ) … ])
for i in range(start, n): …
Space Complexity: O(n * d) (@lru_cache(maxsize=n * d))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
    n = len(jobDifficulty)
    max_job_remaining = jobDifficulty[:]
    for i in range(n - 2, -1, -1):
      max_job_remaining[i] = max(max_job_remaining[i], max_job_remaining[i + 1])
    @lru_cache(maxsize=n * d)
    def min_difiiculty(start=0, _d=d):
      if n - start < _d: return inf
      # if _d == 1: return max(jobDifficulty[start:])
      if _d == 1: return max_job_remaining[start]
      
      # return min([(max(jobDifficulty[start:i + 1]) + min_difiiculty(i + 1, _d - 1)) for i in range(start, n)])
      daily_max_jab_diff, result = 0, inf
      for i in range(start, n): 
        daily_max_jab_diff = max(daily_max_jab_diff, jobDifficulty[i])
        result = min(result, daily_max_jab_diff + min_difiiculty(i + 1, _d - 1))
      return result
    
    return -1 if n < d else min_difiiculty()

Solution: Bottom-Top DP

Time Complexity: O((d * len_) * len_) = O(d * (len_ ** 2))
Space Complexity: O(len_ * d) (@lru_cache(maxsize=len_ * d))
(The input and output generally do not count towards the space complexity.)

Last Updated on 2023/08/18 by A1go