This approach uses a dynamic programming (DP) table to calculate the minimum difficulty schedule. The DP table is constructed such that dp[i][j] represents the minimum difficulty for scheduling the first i jobs in j days. We aim to fill this DP table using a bottom-up approach, iterating over all possible job and day combinations. For each combination, we calculate the scenario where the last day covers a range of jobs and obtains the minimum difficulty possible.
Time Complexity: O(n2d), where n is the length of jobDifficulty and d is the number of days.
Space Complexity: O(nd), due to the storage of minimum difficulties in the DP table.
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int minDifficulty(int* jobDifficulty, int jobDifficultySize, int d) {
6 if (jobDifficultySize < d) return -1;
7 int dp[d+1][jobDifficultySize+1];
8 for (int i = 0; i <= d; ++i) {
9 for (int j = 0; j <= jobDifficultySize; ++j) {
10 dp[i][j] = INT_MAX;
11 }
12 }
13 dp[0][0] = 0;
14
15 for (int day = 1; day <= d; ++day) {
16 for (int job = day; job <= jobDifficultySize; ++job) {
17 int maxDifficulty = 0;
18 for (int k = job; k >= day; --k) {
19 maxDifficulty = (maxDifficulty > jobDifficulty[k-1]) ? maxDifficulty : jobDifficulty[k-1];
20 dp[day][job] = (dp[day][job] < dp[day-1][k-1] + maxDifficulty) ? dp[day][job] : dp[day-1][k-1] + maxDifficulty;
21 }
22 }
23 }
24 return dp[d][jobDifficultySize];
25}
26
27int main() {
28 int jobDifficulty[] = {6,5,4,3,2,1};
29 int d = 2;
30 printf("%d\n", minDifficulty(jobDifficulty, 6, d)); // Output: 7
31 return 0;
32}This implementation initializes a 2D DP table where dp[i][j] keeps track of the minimum difficulty for the first i jobs scheduled in j days. We iterate day by day and within each day, iterate over the possible jobs that can be scheduled. For each possible subarray, we calculate the maximum difficulty and adjust the DP table accordingly.
This approach is based on recursion with memoization. The main idea is to use a recursive function to find the minimum difficulty from a given starting index, splitting the jobs over the remaining days. For each recursive call, consider different partitions for the first day's job and compute the best possible schedule using range maximum queries and storing results to avoid redundant calculations.
Time Complexity: O(n2d), with memoization reducing redundant calculations.
Space Complexity: O(nd), storing calculated subproblems and recursion frames.
1const minDifficulty = (jobDifficulty, d) => {
2 const n = jobDifficulty.length;
3 if (n < d) return -1;
4
5 const memo = Array.from({ length: d + 1 }, () => Array(n).fill(-1));
6
7 const dfs = (idx, days) => {
8 if (days === 1) return Math.max(...jobDifficulty.slice(idx));
9 if (memo[days][idx] !== -1) return memo[days][idx];
10
11 let maxDiff = 0;
12 let result = Infinity;
13 for (let i = idx; i <= n - days; ++i) {
14 maxDiff = Math.max(maxDiff, jobDifficulty[i]);
15 result = Math.min(result, maxDiff + dfs(i + 1, days - 1));
16 }
17
18 return memo[days][idx] = result;
19 }
20
21 return dfs(0, d);
22};
23
24// Usage Example:
25// let jobDifficulty = [6,5,4,3,2,1];
26// let d = 2;
27// console.log(minDifficulty(jobDifficulty, d)); // Output: 7
28The JavaScript solution applies a recursive approach with memoization, using similar logic as the Python solution with array slicing and recursion to identify the minimal total difficulty by balancing the daily job difficulties optimally.