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;

}

在这里插入图片描述