Problem Description
你被安排了 n 个任务。任务需要花费的时间用长度为 n 的整数数组 tasks 表示，第 i 个任务需要花费 tasks[i] 小时完成。一个 工作时间段 中，你可以 至多 连续工作 sessionTime 个小时，然后休息一会儿。
你需要按照如下条件完成给定任务：
给你 tasks 和 sessionTime ，请你按照上述要求，返回完成所有任务所需要的 最少 数目的 工作时间段 。
测试数据保证 sessionTime 大于等于 tasks[i] 中的 最大值 。
note
n == tasks.length1 <= n <= 141 <= tasks[i] <= 10max(tasks[i]) <= sessionTime <= 15
e.g.
示例 1：
1
2
3
4
5
| 输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。
|
示例 2：
1
2
3
4
5
| 输入：tasks = [3,1,3,1,1], sessionTime = 8
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小 时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。
|
示例 3：
1
2
3
| 输入：tasks = [1,2,3,4,5], sessionTime = 15
输出：1
解释：你可以在一个工作时间段以内完成所有任务。
|
Solution
第 256 场周赛周赛第三题，那天早上没爬起来，今天尝试做下，感觉应该是状态压缩的动态规划。不过动态规划始终不会写，就尝试先画递归树，发现重复元素的路径可以压缩（一直没学过状态压缩，难道这就是状态压缩？）就先写个桶记录元素和元素个数，这样就不会走重复路径了。
然后写了个有点别扭的回溯，居然一次过了，看来以后 dp 的题，全用记忆化递归做了是要。。
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
| class Solution {
int ans = 0x3f3f3f3f;
public int minSessions(int[] tasks, int sessionTime) {
int[] bucket = new int[11];
for (int task : tasks) {
bucket[task]++;
}
dfs(bucket, 0, sessionTime, 0, tasks.length);
return ans;
}
public void dfs(int[] bucket, int sum, int sessionTime, int cnt, int len) {
if (len == 0) {
ans = Math.min(cnt + 1, ans);
return;
}
boolean flag = true;
for (int i = 1; i < bucket.length; i++) {
if (bucket[i] > 0 && i + sum <= sessionTime) {
flag = false;
break;
}
}
if (flag) {
dfs(bucket, 0, sessionTime, cnt + 1, len);
} else {
for (int i = 1; i < bucket.length; i++) {
if (bucket[i] > 0 && i + sum <= sessionTime) {
bucket[i]--;
dfs(bucket, i + sum, sessionTime, cnt, len - 1);
bucket[i]++;
}
}
}
}
}
|