2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不
2024-01-03：用go语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time，
分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠，
一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，
开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0，
但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少？
输入：cost = [1,2,3,2], time = [1,2,3,2]。
输出：3。
来自力扣。2742. 给墙壁刷油漆。
答案2024-01-03：
来自左程云。
灵捷3.5
大体过程如下：
paintWalls1?函数
1.paintWalls1函数是基于递归方法的解决方案。
2.在process1函数中，通过递归方式将每种情况下的最小开销计算出来。
3.递归调用时考虑两种情况，选择当前墙刷或者不刷，计算出最小开销。
4.该方法在递归调用的过程中可能会有很多重复计算，效率可能不高。
paintWalls2?函数
1.paintWalls2函数采用了记忆化搜索的方式。
2.定义了一个二维数组dp用于记录已经计算过的结果，避免重复计算。
3.通过递归+记忆化搜索的方式优化了重复计算，提高了效率。
paintWalls3?函数
1.paintWalls3函数采用了动态规划的方式。
2.使用一个一维数组dp保存不同墙数下的最小开销。
3.结合循环和动态递推的方式，迭代计算每墙的最小开销，直到第 n 墙。
时间和空间复杂度
??时间复杂度：
?paintWalls1使用了递归，可能有大量重复计算，其时间复杂度为 O(2^n)。
?paintWalls2和paintWalls3使用了记忆化搜索和动态规划，时间复杂度都为 O(n^2)，其中 n 为墙的数量。
??空间复杂度：
?paintWalls1和paintWalls2的额外空间复杂度为 O(n^2)，因为它们都使用了二维数组存储中间结果。
?paintWalls3的额外空间复杂度为 O(n)，因为它只用了一个一维数组保存中间结果。
go完整代码如下：
package?main
import?(
"fmt"
"math"
)
//?paintWalls1?represents?the?first?function?from?the?given?Java?code.
func?paintWalls1(cost?[]int,?time?[]int)?int?{
return?process1(cost,?time,?0,?len(cost))
}
//?process1?is?the?recursive?function?as?mentioned?in?the?Java?code.
func?process1(cost?[]int,?time?[]int,?i?int,?s?int)?int?{
if?s?<=?0?{
return?0
}
//?s?>?0
if?i?==?len(cost)?{
return?math.MaxInt32
}?else?{
p1?:=?process1(cost,?time,?i+1,?s)
p2?:=?math.MaxInt32
next2?:=?process1(cost,?time,?i+1,?s-1-time[i])
if?next2?!=?math.MaxInt32?{
p2?=?cost[i]?+?next2
}
return?int(math.Min(float64(p1),?float64(p2)))
}
}
//?paintWalls2?is?the?second?function?from?the?given?Java?code.
func?paintWalls2(cost?[]int,?time?[]int)?int?{
n?:=?len(cost)
dp?:=?make([][]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?make([]int,?n+1)
for?j?:=?range?dp[i]?{
dp[i][j]?=?-1
}
}
return?process2(cost,?time,?0,?n,?dp)
}
//?process2?represents?the?recursive?function?in?the?second?approach?of?the?Java?code.
func?process2(cost?[]int,?time?[]int,?i?int,?s?int,?dp?[][]int)?int?{
if?s?<=?0?{
return?0
}
if?dp[i][s]?!=?-1?{
return?dp[i][s]
}
var?ans?int
if?i?==?len(cost)?{
ans?=?math.MaxInt32
}?else?{
p1?:=?process2(cost,?time,?i+1,?s,?dp)
p2?:=?math.MaxInt32
next2?:=?process2(cost,?time,?i+1,?s-1-time[i],?dp)
if?next2?!=?math.MaxInt32?{
p2?=?cost[i]?+?next2
}
ans?=?int(math.Min(float64(p1),?float64(p2)))
}
dp[i][s]?=?ans
return?ans
}
//?paintWalls3?is?the?third?function?from?the?given?Java?code.
func?paintWalls3(cost?[]int,?time?[]int)?int?{
n?:=?len(cost)
dp?:=?make([]int,?n+1)
for?i?:=?range?dp?{
dp[i]?=?math.MaxInt32
}
dp[0]?=?0
for?i?:=?n?-?1;?i?>=?0;?i--?{
for?s?:=?n;?s?>=?1;?s--?{
if?s-1-time[i]?<=?0?{
dp[s]?=?int(math.Min(float64(dp[s]),?float64(cost[i])))
}?else?if?dp[s-1-time[i]]?!=?math.MaxInt32?{
dp[s]?=?int(math.Min(float64(dp[s]),?float64(cost[i]+dp[s-1-time[i]])))
}
}
}
return?dp[n]
}
func?main()?{
cost?:=?[]int{1,?2,?3,?2}
time?:=?[]int{1,?2,?3,?2}
fmt.Println("Result?1:",?paintWalls1(cost,?time))
fmt.Println("Result?2:",?paintWalls2(cost,?time))
fmt.Println("Result?3:",?paintWalls3(cost,?time))
}
在这里插入图片描述rust完整代码如下：
fn?paint_walls1(cost:?Vec,?time:?Vec)?->?i32?{
process1(&cost,?&time,?0,?cost.len()?as?i32)
}
fn?process1(cost:?&Vec,?time:?&Vec,?i:?i32,?s:?i32)?->?i32?{
if?s?<=?0?{
return?0;
}
if?(i?as?usize)?==?cost.len()?{
return?i32::MAX;
}?else?{
let?p1?=?process1(cost,?time,?i?+?1,?s);
let?mut?p2?=?i32::MAX;
let?next2?=?process1(cost,?time,?i?+?1,?s?-?1?-?time[i?as?usize]);
if?next2?!=?i32::MAX?{
p2?=?cost[i?as?usize]?+?next2;
}
return?p1.min(p2);
}
}
fn?paint_walls2(cost:?Vec,?time:?Vec)?->?i32?{
let?n?=?cost.len();
let?mut?dp?=?vec![vec![-1;?n?+?1];?n?+?1];
process2(&cost,?&time,?0,?n?as?i32,?&mut?dp)
}
fn?process2(cost:?&Vec,?time:?&Vec,?i:?i32,?s:?i32,?dp:?&mut?Vec<Vec>)?->?i32?{
if?s?<=?0?{
return?0;
}
if?dp[i?as?usize][s?as?usize]?!=?-1?{
return?dp[i?as?usize][s?as?usize];
}
let?ans;
if?(i?as?usize)?==?cost.len()?{
ans?=?i32::MAX;
}?else?{
let?p1?=?process2(cost,?time,?i?+?1,?s,?dp);
let?mut?p2?=?i32::MAX;
let?next2?=?process2(cost,?time,?i?+?1,?s?-?1?-?time[i?as?usize],?dp);
if?next2?!=?i32::MAX?{
p2?=?cost[i?as?usize]?+?next2;
}
ans?=?p1.min(p2);
}
dp[i?as?usize][s?as?usize]?=?ans;
ans
}
fn?paint_walls3(cost:?Vec,?time:?Vec)?->?i32?{
let?n?=?cost.len();
let?mut?dp?=?vec![i32::MAX;?n?+?1];
dp[0]?=?0;
for?i?in?(0..n).rev()?{
for?s?in?(1..=n?as?i32).rev()?{
if?s?-?1?-?time[i]?<=?0?{
dp[s?as?usize]?=?dp[s?as?usize].min(cost[i]);
}?else?if?dp[(s?-?1?-?time[i])?as?usize]?!=?i32::MAX?{
dp[s?as?usize]?=?dp[s?as?usize].min(cost[i]?+?dp[(s?-?1?-?time[i])?as?usize]);
}
}
}
dp[n]
}
fn?main()?{
let?cost?=?vec![1,?2,?3,?2];
let?time?=?vec![1,?2,?3,?2];
let?result1?=?paint_walls1(cost.clone(),?time.clone());
let?result2?=?paint_walls2(cost.clone(),?time.clone());
let?result3?=?paint_walls3(cost.clone(),?time.clone());
println!("Result?for?paint_walls1:?{}",?result1);
println!("Result?for?paint_walls2:?{}",?result2);
println!("Result?for?paint_walls3:?{}",?result3);
}
在这里插入图片描述c++完整代码如下：
#include
#include
#include
using?namespace?std;
//?暴力递归
int?process1(vector&?cost,?vector&?time,?int?i,?int?s)?{
if?(s?<=?0)?{
return?0;
}
if?(i?==?cost.size())?{
return?INT_MAX;
}
else?{
int?p1?=?process1(cost,?time,?i?+?1,?s);
int?p2?=?INT_MAX;
int?next2?=?process1(cost,?time,?i?+?1,?s?-?1?-?time[i]);
if?(next2?!=?INT_MAX)?{
p2?=?cost[i]?+?next2;
}
return?min(p1,?p2);
}
}
int?paintWalls1(vector&?cost,?vector&?time)?{
return?process1(cost,?time,?0,?cost.size());
}
//?暴力递归改记忆化搜索
int?process2(vector&?cost,?vector&?time,?int?i,?int?s,?vector<vector>&?dp)?{
if?(s?<=?0)?{
return?0;
}
if?(dp[i][s]?!=?-1)?{
return?dp[i][s];
}
int?ans;
if?(i?==?cost.size())?{
ans?=?INT_MAX;
}
else?{
int?p1?=?process2(cost,?time,?i?+?1,?s,?dp);
int?p2?=?INT_MAX;
int?next2?=?process2(cost,?time,?i?+?1,?s?-?1?-?time[i],?dp);
if?(next2?!=?INT_MAX)?{
p2?=?cost[i]?+?next2;
}
ans?=?min(p1,?p2);
}
dp[i][s]?=?ans;
return?ans;
}
int?paintWalls2(vector&?cost,?vector&?time)?{
int?n?=?cost.size();
vector<vector>?dp(n?+?1,?vector(n?+?1,?-1));
return?process2(cost,?time,?0,?n,?dp);
}
//?严格位置依赖的动态规划?+?空间压缩
int?paintWalls3(vector&?cost,?vector&?time)?{
int?n?=?cost.size();
vectordp(n?+?1,?INT_MAX);
dp[0]?=?0;
for?(int?i?=?n?-?1;?i?>=?0;?i--)?{
for?(int?s?=?n;?s?>=?1;?s--)?{
if?(s?-?1?-?time[i]?<=?0)?{
dp[s]?=?min(dp[s],?cost[i]);
}
else?if?(dp[s?-?1?-?time[i]]?!=?INT_MAX)?{
dp[s]?=?min(dp[s],?cost[i]?+?dp[s?-?1?-?time[i]]);
}
}
}
return?dp[n];
}
int?main()?{
vectorcost?=?{?1,?2,?3,?2?};
vectortime?=?{?1,?2,?3,?2?};
cout?<
cout?<
cout?<
return?0;
}
在这里插入图片描述c语言完整代码如下：
#include
#include
#include
int?process1(int*?cost,?int*?time,?int?i,?int?s,?int?costSize);
int?paintWalls1(int*?cost,?int?costSize,?int*?time,?int?timeSize)?{
return?process1(cost,?time,?0,?costSize,?costSize);
}
int?process1(int*?cost,?int*?time,?int?i,?int?s,?int?costSize)?{
if?(s?<=?0)?{
return?0;
}
if?(i?==?costSize)?{
return?INT_MAX;
}
else?{
int?p1?=?process1(cost,?time,?i?+?1,?s,?costSize);
int?p2?=?INT_MAX;
int?next2?=?process1(cost,?time,?i?+?1,?s?-?1?-?time[i],?costSize);
if?(next2?!=?INT_MAX)?{
p2?=?cost[i]?+?next2;
}
return?(p1?<?p2)???p1?:?p2;
}
}
int?process2(int*?cost,?int*?time,?int?i,?int?s,?int?costSize,?int**?dp);
int?paintWalls2(int*?cost,?int?costSize,?int*?time,?int?timeSize)?{
int**?dp?=?(int**)malloc((costSize?+?1)?*?sizeof(int*));
for?(int?i?=?0;?i?<=?costSize;?i++)?{
dp[i]?=?(int*)malloc((costSize?+?1)?*?sizeof(int));
for?(int?j?=?0;?j?<=?costSize;?j++)?{
dp[i][j]?=?-1;
}
}
int?result?=?process2(cost,?time,?0,?costSize,?costSize,?dp);
for?(int?i?=?0;?i?<=?costSize;?i++)?{
free(dp[i]);
}
free(dp);
return?result;
}
int?process2(int*?cost,?int*?time,?int?i,?int?s,?int?costSize,?int**?dp)?{
if?(s?<=?0)?{
return?0;
}
if?(dp[i][s]?!=?-1)?{
return?dp[i][s];
}
int?ans;
if?(i?==?costSize)?{
ans?=?INT_MAX;
}
else?{
int?p1?=?process2(cost,?time,?i?+?1,?s,?costSize,?dp);
int?p2?=?INT_MAX;
int?next2?=?process2(cost,?time,?i?+?1,?s?-?1?-?time[i],?costSize,?dp);
if?(next2?!=?INT_MAX)?{
p2?=?cost[i]?+?next2;
}
ans?=?(p1?<?p2)???p1?:?p2;
}
dp[i][s]?=?ans;
return?ans;
}
int?paintWalls3(int*?cost,?int?costSize,?int*?time,?int?timeSize);
int?paintWalls3(int*?cost,?int?costSize,?int*?time,?int?timeSize)?{
int*?dp?=?(int*)malloc((costSize?+?1)?*?sizeof(int));
for?(int?i?=?0;?i?<=?costSize;?i++)?{
dp[i]?=?INT_MAX;
}
dp[0]?=?0;
for?(int?i?=?costSize?-?1;?i?>=?0;?i--)?{
for?(int?s?=?costSize;?s?>=?1;?s--)?{
if?(s?-?1?-?time[i]?<=?0)?{
dp[s]?=?(dp[s]?<?cost[i])???dp[s]?:?cost[i];
}
else?if?(dp[s?-?1?-?time[i]]?!=?INT_MAX)?{
dp[s]?=?(dp[s]?<?cost[i]?+?dp[s?-?1?-?time[i]])???dp[s]?:?cost[i]?+?dp[s?-?1?-?time[i]];
}
}
}
int?result?=?dp[costSize];
free(dp);
return?result;
}
int?main()?{
int?cost[]?=?{?1,?2,?3,?2?};
int?time[]?=?{?1,?2,?3,?2?};
int?result1?=?paintWalls1(cost,?4,?time,?4);
printf("Result?of?paintWalls1:?%d\n",?result1);
int?result2?=?paintWalls2(cost,?4,?time,?4);
printf("Result?of?paintWalls2:?%d\n",?result2);
int?result3?=?paintWalls3(cost,?4,?time,?4);
printf("Result?of?paintWalls3:?%d\n",?result3);
return?0;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OiGc4vgAgkiwjjOTDQSG2gWQ0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
