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.
1using System;
2
3public class Solution {
4 public int MinDifficulty(int[] jobDifficulty, int d) {
5 int n = jobDifficulty.Length;
6 if (n < d) return -1;
7 int[,] dp = new int[d + 1, n + 1];
8 for (int i = 0; i <= d; i++)
9 for (int j = 0; j <= n; j++)
10 dp[i, j] = int.MaxValue;
11 dp[0, 0] = 0;
12
13 for (int day = 1; day <= d; ++day) {
14 for (int job = day; job <= n; ++job) {
15 int maxDifficulty = 0;
16 for (int k = job; k >= day; --k) {
17 maxDifficulty = Math.Max(maxDifficulty, jobDifficulty[k - 1]);
18 dp[day, job] = Math.Min(dp[day, job], dp[day - 1, k - 1] + maxDifficulty);
19 }
20 }
21 }
22 return dp[d, n];
23 }
24
25 // Example usage:
26 // public static void Main(string[] args) {
27 // Solution sol = new Solution();
28 // int[] jobDifficulty = {6,5,4,3,2,1};
29 // int d = 2;
30 // Console.WriteLine(sol.MinDifficulty(jobDifficulty, d)); // Output: 7
31 // }
32}This C# solution uses a 2D array for the DP table. It builds the solution by iterating over possible day-job pairs and updates the DP array using nested loops that represent possible end days for subarrays of jobs.
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.
1using System;
2using System.Linq;
3
4public class Solution {
5 int[,] memo;
6
7 private int Dfs(int[] jobDifficulty, int d, int idx) {
8 if (d == 1) {
9 return jobDifficulty.Skip(idx).Max();
10 }
11 if (memo[d, idx] != -1) return memo[d, idx];
12
13 int maxDiff = 0, result = int.MaxValue;
14 for (int i = idx; i <= jobDifficulty.Length - d; ++i) {
15 maxDiff = Math.Max(maxDiff, jobDifficulty[i]);
16 result = Math.Min(result, maxDiff + Dfs(jobDifficulty, d - 1, i + 1));
17 }
18 return memo[d, idx] = result;
19 }
20
21 public int MinDifficulty(int[] jobDifficulty, int d) {
22 int n = jobDifficulty.Length;
23 if (n < d) return -1;
24 memo = new int[d + 1, n];
25 for (int i = 0; i <= d; i++)
26 for (int j = 0; j < n; j++)
27 memo[i, j] = -1;
28 return Dfs(jobDifficulty, d, 0);
29 }
30
31 // Example usage:
32 // public static void Main(string[] args) {
33 // Solution sol = new Solution();
34 // int[] jobDifficulty = {6,5,4,3,2,1};
35 // int d = 2;
36 // Console.WriteLine(sol.MinDifficulty(jobDifficulty, d)); // Output: 7
37 // }
38}The C# solution implements the recursive DFS approach with memoization using a 2D array that store results for subproblems. It chooses optimal job partition points by balancing the maximum difficulty for each subproblem.