job_scheduling.py

from typing import List, Mapping


class Solution:
    dp: Mapping[int, Mapping[int, int]] = {}

    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        self.jobDifficulty = jobDifficulty
        self.n = len(jobDifficulty)
        self.d = d
        for i in range(self.n):
            self.dp[i] = dict([(j, None) for j in range(self.d)])
        return self.get(self.n - 1, self.d - 1)

    def get(self, n: int, d: int) -> int:
        if n < 0 and d < 0:
            return 0
        if n < 0 or d < 0:
            return -1
        if self.dp[n][d] is not None:
            return self.dp[n][d]

        diff_today = -1
        min_diff = 1e20
        for i in range(n, -1, -1):
            diff_today = max(diff_today, self.jobDifficulty[i])
            past_diff = self.get(i - 1, d - 1)
            if past_diff != -1:
                min_diff = min(min_diff, past_diff + diff_today)
        self.dp[n][d] = -1 if min_diff == 1e20 else min_diff
        return self.dp[n][d]


if __name__ == '__main__':
    s = Solution()
    print(s.minDifficulty([6, 5, 4, 3, 2, 1], 2))
    print(s.minDifficulty([9, 9, 9], 4))
    print(s.minDifficulty([1, 1, 1], 3))
    print(s.minDifficulty([7, 1, 7, 1, 7, 1], 3))
    print(s.minDifficulty([11, 111, 22, 222, 33, 333, 44, 444], 6))