leetcode 1335

问题

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th 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 in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].

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

Example 1:

img

1
2
3
4
5
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:

1
2
3
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:

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

Example 4:

1
2
Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

1
2
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

Constraints:

  • 1 <= jobDifficulty.length <= 300
  • 0 <= jobDifficulty[i] <= 1000
  • 1 <= d <= 10

分析（动态规划）

分析可知，该问题可以等价转换：给定一个数组 $jobDifficulty[]$ ，将数组划分为连续的 $d$ 段，每段中最大的那么元素作为该段的代表元素，求一种划分方案使这 $d$ 个代表元素之和最小，输出这个最小值。若不能完成划分则输出 $-1$。首先想到的是动态规划的解法。另 $dp[i][j]$ 表示将从 $jobDifficulty[i]$ 开始到该数组结尾的所有元素划分成 $j$ 段，每段中最大的那么元素作为该段的代表元素时的最小值。则有状态转移方程：
$$
dp[i][j] = \min \limits_{i\leq k\leq n-j}\{\max \limits_{i\leq x\leq k}jobDifficulty[x] + dp[k+1][j-1]\}
$$
观察状态转移方程可知，我们可以将分段数来作为 DP 的阶段。

目标：$dp[0][d]$，初始条件：$dp[i][1] = \max \limits_{i \leq x \leq n-1}jobDifficulty[x]$。

代码（动态规划）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        if (d > n) return -1;

        vector<vector<int>> dp(n, vector<int>(d+1));
        dp[n-1][1] = jobDifficulty.back();
        for (int i = n-2; i >= 0; --i) {
            dp[i][1] = max(dp[i+1][1], jobDifficulty[i]);
        }

        for (int j = 2; j <= d; ++j) {
            for (int i = 0; i <= n-j; ++i) {
                int mx   = INT_MIN;
                dp[i][j] = INT_MAX;   // 只可以参加比较运算，不能用来参加算数运算
                for (int k = i; k <= n-j; ++k) {
                    mx = max(mx, jobDifficulty[k]);
                    dp[i][j] = min(dp[i][j], dp[k+1][j-1] + mx);
                }
            }
        }
        return dp[0][d];
    }

};

数组压缩之后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        int n = jobDifficulty.size();
        if (d > n) return -1;
        vector<int> dp(n);
        dp[n-1] = jobDifficulty.back();
        for (int i = n-2; i >= 0; --i) {
            dp[i] = max(dp[i+1], jobDifficulty[i]);
        }
        for (int j = 2; j <= d; ++j) {
            for (int i = 0; i <= n-j; ++i) {
                int mx = INT_MIN;
                dp[i]  = INT_MAX;   // 只可以参加比较运算，不能用来参加算数运算
                for (int k = i; k <= n-j; ++k) {
                    mx = max(mx, jobDifficulty[k]);
                    dp[i] = min(dp[i], dp[k+1] + mx);
                }
            }
        }
        return dp[0];
    }
};

分析（动态规划+单调栈）

江湖传闻可以使用单调栈来由优化内层的循环，从而降低一个数量级的时间复杂度。但大多只有代码没有分析过程，分析了一通还是没有分析好，暂时先收藏起来。等日后再处理一下。

代码（动态规划+单调栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution 
{
    struct segment
    {
        int imaxjob;    //  index of max complexity job this segment
        int min;        //  local min this segment
    };
    
public:

    int minDifficulty(vector<int>& jobs, int days) 
    {
        int n = jobs.size();   if (n < days)  return -1;
 
        vector<int> dp{ jobs[0] };  for (int j = 1; j < n; j++)  dp.push_back( max(dp[j-1], jobs[j]) );
		// dp[i] 表示jobs[0...i] 分配为 d 天的最小值

        // for (int d = 1; d < days; d++)
        for (int d = 1; d < days; d++)
        {
            stack<segment> s;  int t = dp[d - 1];  
            
            // jobs[0...d-1] 被分为 d 段是唯一的，不需要计算。
            // 所以从 j = d 开始
            for (int j = d; j < n; j++)
            {
                // t 表示dp[d-1] 前 d 个数被分成
                int m = t;  t = dp[j];           
                // 按照jobs[i]的降序进行排列
                // 栈底最大，栈顶最小
                while (!s.empty() && jobs[s.top().imaxjob] <= jobs[j])
                {
                    m = min(m, s.top().min);
                    s.pop();
                }
                
                dp[j] = !s.empty() ? min(dp[s.top().imaxjob], m + jobs[j]) : (m + jobs[j]);
                s.push({ .imaxjob = j, .min = m });
            }
        }
        
        return dp[n-1];
    }
};