考点
思路
首先第一个易错点，是不可以贪心的
如果你尝试先取开销短的，开销短的里面取时间小的
比如有cost = {2, 2, 3, 4}，time = {1, 1, 4, 1}，那么会取第一个和第二个，最终开销为2 + 2 = 4
但实际上应该只取第三个，最终开销为3
如果你尝试先取时间长的，时间相同的里面取开销小的
比如有cost = {3, 2, 2, 4}，time = {2, 1, 1, 1}，那么会取第一个和第二个，最终开销为2 + 3 = 5
实际上应该只取第二个和第三个，最终开销为4
第二个易错点，你可能会设如下转移方程：
1
2
| f[i][j], 刷前i个墙有j次免费机会
f[i][j] = min(f[i-1][j+1]（刷第i个墙免费，用一次免费机会）, f[i-1][j - time[i]] + cost[i]（刷第i个墙付费）)
|
然后得到如下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
static const int maxn = 5e2 + 50, inf = 0x3f3f3f3f;
int n, f[maxn][maxn];
int paintWalls(vector<int>& cost, vector<int>& time) {
n = cost.size();
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
if (j + 1 <= n) f[i][j] = min(f[i][j], f[i - 1][j + 1]);
if (j >= time[i - 1])
f[i][j] = min(f[i][j], f[i - 1][j - time[i - 1]] + cost[i - 1]);
}
}
int res = inf;
for (int i = 0; i <= n; ++i) res = min(res, f[n][i]);
return res;
}
};
|
这就是经典的错误，因为前i个墙的免费机会，和后面i + 1 ~ n个墙也有关系，并不能保证DAG图
比如一共4面墙，取第一个和第四个是最优解，然而取完第四面墙增加的免费机会回头影响前面的结果，这违背了DP的原则
对于第i个墙，如果选择刷它，那么一共可以刷time[i] + 1面墙，+ 1是刷当前墙，并且该性质并不会被顺序所影响，所以考虑新的转移方程：
令
n = cost.size()w_i = time[i] + 1 表示选第 i
个付费工人能覆盖的墙数（他自己 1 面 + 免费并行
time[i] 面）。
定义二维 DP：
dp[i][j] = 用前 i 个工人（下标
0..i-1）能覆盖“至少 j 面墙”的最小花费。
初始条件为：
这里选择Push方向比较好写，即从当前状态转移到下一个状态，传统的Pull方向有点难理解
- 不选：
dp[i+1][j] = min(dp[i+1][j], dp[i][j])
- 选： 已有覆盖
j，选后到
j' = min(n, j + w_i)， 转移
dp[i+1][j'] = min(dp[i+1][j'], dp[i][j] + cost[i])
那么得到最终答案答案 = dp[n][n]（使用全部 n
个工人“可选可不选”后，覆盖至少 n 面的最小花费）
得到最终的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
static const int maxn = 5e2 + 50, inf = 0x3f3f3f3f;
int n, f[maxn][maxn];
int paintWalls(vector<int>& cost, vector<int>& time) {
n = cost.size();
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n; ++j) {
int c = cost[i], w = time[i] + 1;
f[i + 1][j] = min(f[i + 1][j], f[i][j]);
f[i + 1][min(n, j + w)] = min(f[i + 1][min(n, j + w)], f[i][j] + c);
}
}
return f[n][n];
}
};
|
当然，由于长得很像01背包，所以可以选择原地滚动数组，减少常数开销：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
static const int maxn = 5e2 + 50, inf = 0x3f3f3f3f;
int n, f[maxn];
int paintWalls(vector<int>& cost, vector<int>& time) {
n = cost.size(), memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = n; j >= 0; --j) {
int c = cost[i], w = time[i] + 1, mi = min(n, j + w);
f[mi] = min(f[mi], f[j] + c);
}
}
return f[n];
}
};
|