1335. Minimum Difficulty of a Job Schedule

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

class Solution {
    int dp[301][11];
    int solution(vector<int>& job, int p, int d) {
        if(dp[p][d] != -1) return dp[p][d];
        if(d == 1) return dp[p][d] = *max_element(job.begin() + p, job.end());
        int ma = 0;
        int& res = dp[p][d] = INT_MAX;
        for(int i = p; i <= job.size() - d; i++) {
            ma = max(ma, job[i]);
            res = min(res, solution(job, i+1, d-1) + ma);
        }
        return res;
    }
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        if(jobDifficulty.size() < d) return -1;
        memset(dp,-1,sizeof(dp));
        return solution(jobDifficulty, 0, d);
    }
};