Minimum Difficulty of a Job Schedule

lcpy gen -n 1335   # by problem number
lcpy gen -s minimum_difficulty_of_a_job_schedule   # by problem name

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day, total difficulty = 3.

from itertools import accumulate


class Solution:
    def min_difficulty(self, job_difficulty: list[int], d: int) -> int:
        n = len(job_difficulty)
        if n < d:
            return -1
        inf = 10**9
        dp = list(accumulate(job_difficulty, max))
        for day in range(1, d):
            ndp = [inf] * n
            for i in range(day, n):
                run_max = 0
                for j in range(i, day - 1, -1):
                    run_max = max(run_max, job_difficulty[j])
                    ndp[i] = min(ndp[i], dp[j - 1] + run_max)
            dp = ndp
        return dp[n - 1]