1335. Minimum Difficulty of a Job Schedule - Explanation

1. Dynamic Programming (Top-Down)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = {}

        def dfs(i, d, cur_max):
            if i == n:
                return 0 if d == 0 else float("inf")
            if d == 0:
                return float("inf")
            if (i, d, cur_max) in dp:
                return dp[(i, d, cur_max)]

            cur_max = max(cur_max, jobDifficulty[i])
            res = min(
                dfs(i + 1, d, cur_max),
                cur_max + dfs(i + 1, d - 1, -1)
            )
            dp[(i, d, cur_max)] = res
            return res

        return dfs(0, d, -1)

Time & Space Complexity

Time complexity: $O(n * d * m)$
Space complexity: $O(n * d * m)$

Where $n$ is the number of jobs, $d$ is the number of days, and $m$ is the maximum difficulty value among all the job difficulties.

2. Dynamic Programming (Top-Down Optimized)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = {}

        def dfs(i, d):
            if (i, d) in dp:
                return dp[(i, d)]

            maxi = jobDifficulty[i]
            if d == 1:
                idx = i
                while i < n:
                    maxi = max(maxi, jobDifficulty[i])
                    i += 1
                dp[(idx, d)] = maxi
                return maxi

            res = float("inf")
            for j in range(i + 1, n):
                res = min(res, maxi + dfs(j, d - 1))
                maxi = max(maxi, jobDifficulty[j])
            dp[(i, d)] = res
            return res

        return dfs(0, d)

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n * d)$

Where $n$ is the number of jobs and $d$ is the number of days.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = [[float("inf")] * (d + 1) for _ in range(n + 1)]
        dp[n][0] = 0

        for day in range(1, d + 1):
            for i in range(n - 1, -1, -1):
                maxi = 0
                for j in range(i, n - day + 1):
                    maxi = max(maxi, jobDifficulty[j])
                    dp[i][day] = min(dp[i][day], maxi + dp[j + 1][day - 1])

        return dp[0][d]

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n * d)$

Where $n$ is the number of jobs and $d$ is the number of days.

4. Dynamic Programming (Space Optimized)

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if len(jobDifficulty) < d:
            return -1

        n = len(jobDifficulty)
        dp = [float("inf")] * (n + 1)
        dp[n] = 0

        for day in range(1, d + 1):
            for i in range(n - day + 1):
                maxi = 0
                dp[i] = float("inf")
                for j in range(i, n - day + 1):
                    maxi = max(maxi, jobDifficulty[j])
                    dp[i] = min(dp[i], maxi + dp[j + 1])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n ^ 2 * d)$
Space complexity: $O(n)$

Where $n$ is the number of jobs and $d$ is the number of days.

5. Monotonic Decreasing Stack

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1

        dp = [float("inf")] * n
        for day in range(1, d + 1):
            next_dp = [float("inf")] * n
            stack = []
            for i in range(day - 1, n):
                next_dp[i] = dp[i - 1] + jobDifficulty[i] if i > 0 else jobDifficulty[i]
                while stack and jobDifficulty[stack[-1]] <= jobDifficulty[i]:
                    j = stack.pop()
                    next_dp[i] = min(next_dp[i], next_dp[j] - jobDifficulty[j] + jobDifficulty[i])
                if stack:
                    next_dp[i] = min(next_dp[i], next_dp[stack[-1]])
                stack.append(i)
            dp = next_dp

        return dp[-1]

Time & Space Complexity

Time complexity: $O(n * d)$
Space complexity: $O(n)$

Where $n$ is the number of jobs and $d$ is the number of days.