1
2024-01-03：用 go 语言，给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time， 分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠， 一位需要 付费 的油漆匠
作者：福大大架构师每日一题
- 2024-01-03 北京
本文字数：5837 字
阅读完需：约 19 分钟
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：
来自左程云。
大体过程如下：
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<i32>, time: Vec<i32>) -> i32 { process1(&cost, &time, 0, cost.len() as i32)}
fn process1(cost: &Vec<i32>, time: &Vec<i32>, 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<i32>, time: Vec<i32>) -> 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<i32>, time: &Vec<i32>, i: i32, s: i32, dp: &mut Vec<Vec<i32>>) -> 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<i32>, time: Vec<i32>) -> 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 <iostream>#include <vector>#include <algorithm>using namespace std;
// 暴力递归int process1(vector<int>& cost, vector<int>& 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<int>& cost, vector<int>& time) { return process1(cost, time, 0, cost.size());}
// 暴力递归改记忆化搜索int process2(vector<int>& cost, vector<int>& time, int i, int s, vector<vector<int>>& 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<int>& cost, vector<int>& time) { int n = cost.size(); vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1)); return process2(cost, time, 0, n, dp);}
// 严格位置依赖的动态规划 + 空间压缩int paintWalls3(vector<int>& cost, vector<int>& time) { int n = cost.size(); vector<int> dp(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() { vector<int> cost = { 1, 2, 3, 2 }; vector<int> time = { 1, 2, 3, 2 };
cout << "Result for paintWalls1: " << paintWalls1(cost, time) << endl; cout << "Result for paintWalls2: " << paintWalls2(cost, time) << endl; cout << "Result for paintWalls3: " << paintWalls3(cost, time) << endl;
return 0;}
复制代码
c 语言完整代码如下：
#include <stdio.h>#include <stdlib.h>#include <limits.h>
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;}
复制代码
划线
评论
复制
发布于: 23 分钟前阅读数: 5
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/ed730247fbdb83f9ef390ec74】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
评论