题目描述
给你两个长度为 n
下标从 0 开始的整数数组 cost
和 time
,分别表示给 n
堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠:
- 一位需要 付费 的油漆匠,刷第
i
堵墙需要花费time[i]
单位的时间,开销为cost[i]
单位的钱。 - 一位 免费 的油漆匠,刷 任意 一堵墙的时间为
1
单位,开销为0
。但是必须在付费油漆匠 工作 时,免费油漆匠才会工作。
请你返回刷完 n
堵墙最少开销为多少。
样例
输入:cost = [1,2,3,2], time = [1,2,3,2]
输出:3
解释:下标为 0 和 1 的墙由付费油漆匠来刷,需要 3 单位时间。
同时,免费油漆匠刷下标为 2 和 3 的墙,需要 2 单位时间,开销为 0。
总开销为 1 + 2 = 3。
输入:cost = [2,3,4,2], time = [1,1,1,1]
输出:4
解释:下标为 0 和 3 的墙由付费油漆匠来刷,需要 2 单位时间。
同时,免费油漆匠刷下标为 1 和 2 的墙,需要 2 单位时间,开销为 0。
总开销为 2 + 2 = 4。
限制
1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 10^6
1 <= time[i] <= 500
算法
(动态规划) $O(n^2T)$
- 由于免费油漆匠的工作时间完全取决于付费油漆匠,所以我们需要尽可能地找到开销低且工作时间长,刷的墙又多的付费油漆匠。最终需要保证,付费油漆匠的工作时间需要大于等于付费油漆匠没有刷的墙数,也就是付费油漆匠的工作时间与刷的墙数累计需要超过总墙数 $n$。
- 设状态 $f(i, j)$ 表示考察了前 $i$ 堵墙,付费油漆匠工作时间与刷的墙数总和为 $j$ 时的最小开销。其中 $i$ 的有效下标从 $1$ 开始。
- 初始时,$f(0, 0) = 0$,其余为正无穷待定。
- 转移时,对于 $f(i, j)$,可以选择不让付费粉刷匠刷当前的墙,则 $f(i, j) = f(i - 1, j)$。如果让付费粉刷匠刷,则需要保证 $j >= times(i) + 1$,转移 $f(i, j) = f(i - 1, j - time(i) + 1) + cost(i)$。二者取最小值。
- 最终答案为 $\min_{j=n}^{m}{f(n, j)}$,其中 $m$ 表示最大可能的工作时间加刷的墙数。
- 可以通过倒序枚举第二维,省略掉第一维的定义。
时间复杂度
- 状态数为 $O(n^2T)$,转移时间为常数,故总时间复杂度为 $O(n^2T)$。
空间复杂度
- 优化掉第一维后,需要 $O(nT)$ 的空间存储状态。
C++ 代码
const int N = 250510;
class Solution {
private:
int f[N];
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
const int n = cost.size();
int m = 0;
memset(f, 0x7f, sizeof(f));
f[0] = 0;
for (int i = 0; i < n; i++) {
m += time[i] + 1;
for (int j = m; j >= time[i] + 1; j--)
f[j] = min(f[j], f[j - time[i] - 1] + cost[i]);
}
int ans = INT_MAX;
for (int j = n; j <= m; j++)
ans = min(ans, f[j]);
return ans;
}
};