题目描述
你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。 你需要按照如下条件完成给定任务： 如果你在某一个时间段开始一个任务，你需要在 同一个 时间段完成它。 完成一个任务后，你可以 立马 开始一个新的任务。 你可以按 任意顺序 完成任务。 给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。 测试数据保证 sessionTime 大于等于 tasks[i] 中的 最大值 。
Example 1:
输入：tasks = [1,2,3], sessionTime = 3 输出：2 解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。
Example 2:
输入：tasks = [3,1,3,1,1], sessionTime = 8 输出：2 解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。
Example 3:
输入：tasks = [1,2,3,4,5], sessionTime = 15 输出：1 解释：你可以在一个工作时间段以内完成所有任务。
Constraints:
- n == tasks.length
- 1 <= n <= 14
- 1 <= tasks[i] <= 10
- max(tasks[i]) <= sessionTime <= 15
解题思路
- dp状态数组压缩，没看太懂
C++代码
class Solution {
public:
int minSessions(vector<int>& tasks, int sessionTime) {
int n = tasks.size();
int N = 1 << n;
int dp[N];
memset(dp, 0x3f, sizeof(dp));
for(int i = 1; i < N; i++){
int spend = 0;
int state = i;
int idx = 0;
while(state){
spend += (state & 1) ? tasks[idx] : 0;
idx++;
state >>= 1;
}
if(spend <= sessionTime){
dp[i] = 1;
}
}
for(int i = 1; i < N; i++){
if(dp[i] == 1){
continue;
}
for(int j = 0; j < i; j++){
if((i | j) == i){
dp[i] = min(dp[i], dp[i - j] + dp[j]);
}
}
}
return dp[N - 1];
}
};
