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 &lt;= j &lt; 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.

&nbsp;
Example 1:

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 


Example 2:

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.


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= jobDifficulty.length &lt;= 300
	0 &lt;= jobDifficulty[i] &lt;= 1000
	1 &lt;= d &lt;= 10


class Solution:
    def solve(self, nums, index, d):
        if index == len(nums) or d == 1:
            #print(max(nums[index:]))
            return max(nums[index:])
        ans = float("inf")
        for i in range(index, len(nums)-d+1):
            curr = max(nums[index:i+1]) + self.solve(nums, i+1, d-1)
            ans = min(ans, curr)
        return ans
    
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        ans = self.solve(jobDifficulty, 0, d)
        if ans == float("inf"):
            return -1
        else:
            return ans
class Solution {
    // Given an array, cut it into d contiguous subarray and return the minimum sum of max of each subarray.
    public int minDifficulty(int[] jobDifficulty, int d) {
        if(d>jobDifficulty.length){
            return -1;
        }
        
        int[][] memo = new int[d+1][jobDifficulty.length];
        for(int[] m : memo){
            Arrays.fill(m, -1);
        }
        
        return getMinDays(jobDifficulty, d, memo, 0);
    }
    
    private int getMinDays(int[] jobDifficulty, int d, int[][] memo, int idx){
        if(d==1){
            int max=0;
            while(idx < jobDifficulty.length){
                max=Math.max(max, jobDifficulty[idx]);
                idx++;
            }
            return max;
        }
        
        if(memo[d][idx] != -1) return memo[d][idx];
        
        int max=0;
        int res=Integer.MAX_VALUE;
        // [6,5,4,3,2,1], d=5 => we don't want the cut at 4th position in the array because we won't be able to divide it into 5 parts
        for(int i=idx; i<jobDifficulty.length-d+1; i++){
            max = Math.max(max, jobDifficulty[i]);
            res = Math.min(res, max + getMinDays(jobDifficulty, d-1, memo, i+1));
        }
        
        memo[d][idx]=res;
        return memo[d][idx];
    }
}
class Solution {
    vector<int> v;
    int len;
    int dp[301][11];
    int dfs(int idx, int d){//n*d
        if(idx>=len)
            return 0;
        if(d==1)
            return *max_element(v.begin()+idx,v.end());
        if(dp[idx][d]!=-1)
            return dp[idx][d];
        int maxx=INT_MIN;
        int res=INT_MAX;
        for(int i=idx;i<=len-d;i++){//n
            maxx=max(v[i],maxx);
            res=min(maxx+dfs(i+1,d-1),res);
        }
        return dp[idx][d]=res;
    }
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        v=jobDifficulty;
        len=v.size();
        if(d>len)
            return -1;
        memset(dp,-1,sizeof(dp));
        return dfs(0,d);
    }
};
var minDifficulty = function(jobDifficulty, d) {
    // don't have enought jobs to distribute
    if (jobDifficulty.length < d) {
        return -1;
    }

    // in dynamic programming top-down approach
    // we need to have memoisation to not repeat calculations
    let memo = new Array(d+1).fill(-1).map(
        () => new Array(jobDifficulty.length+1).fill(-1)
    )

    const dp = function(D, N) {

        // if we calculated this before, just return
        if (-1 != memo[D][N]) {
            return memo[D][N];
        }

        // if we have only 1 day, we just need to take all jobs
        // and return the highest difficulty
        if (1 == D) {
            memo[D][N] = 0;
            for (let i = 0; i < N; i++) {
                if (memo[D][N] < jobDifficulty[i]) {
                    memo[D][N] = jobDifficulty[i];
                }
            }
            return memo[D][N];
        }

        // otherwise, we use our recurrence relation to calculate
        memo[D][N] = 1000 * D;

        let max_job_per_day = N - D + 1;
        let max_difficulty = 0;

        // iteration for recurrence relation
        for (let X = 1; X <= max_job_per_day; X++) {
            // count max in the current range
            // len - X is the starting point for
            // the last day in D days
            if (jobDifficulty[N - X] > max_difficulty) {
                max_difficulty = jobDifficulty[N - X];
            }
            // recurrence relation
            // we took X jobs,
            // so we still have N - X jobs for D - 1 days
            let min_sum = max_difficulty + dp(D - 1, N - X);

            // pick the min only
            if (min_sum < memo[D][N]) {
                memo[D][N] = min_sum;
            }
        }

        return memo[D][N];
    }

    return dp(d, jobDifficulty.length);
}
Minimum Difficulty of a Job Schedule