给你两个长度为 n
下标从 0 开始的整数数组 cost
和 time
,分别表示给 n
堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠:
·
一位需要 付费 的油漆匠,刷第 i
堵墙需要花费 time[i]
单位的时间,开销为 cost[i]
单位的钱。
·
一位 免费 的油漆匠,刷 任意 一堵墙的时间为 1
单位,开销为 0
。但是必须在付费油漆匠 工作 时,免费油漆匠才会工作。
请你返回刷完 n
堵墙最少开销为多少。
示例 1:
输入:cost = [1,2,3,2], time = [1,2,3,2]
输出:3
解释:下标为 0 和 1 的墙由付费油漆匠来刷,需要 3 单位时间。同时,免费油漆匠刷下标为 2 和 3 的墙,需要 2 单位时间,开销为 0 。总开销为 1 + 2 = 3 。
示例 2:
输入: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] <= 106
·1 <= time[i] <= 500
题目大意:在每次付费油漆匠工作时免费油漆匠才工作的情况下计算刷完所有墙的最小开销。
分析:设dp[k]为刷完k个墙壁最少花费的价格。
(1)在遍历数组的过程中,对于第i个元素,需考虑是否将其加入付费油漆匠的工作任务中,因此对dp数组进行一遍维护,根据dp数组的定义对dp[k]进行更新——dp[k]=min(dp[k],dp[max(0,k-1-time[i])]+cost[i]);
(2)在更新dp数组过程中,由于dp数组后面值的更新结果与更新前的dp数组中前面的值有关,因此为了避免前面的值先更新导致后面值的更新结果有误,更新dp数组应从后往前更新。
class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
int N=cost.size();
vector<int> dp(N+1,INT_MAX-1000000);//dp[k]维护刷完k个墙壁最少花费的价格
dp[0]=0;
for(int i=0;i<N;++i){
for(int j=N;j>0;--j){
dp[j]=min(dp[j],dp[max(0,j-1-time[i])]+cost[i]);
}
}
return dp[N];
}
};