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<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;
}

本栏目推荐文章
• 类模板实现简单的数组
• 数组内存图
• 数组
• 整数的划分（递归或动态规划）
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• 吴师兄学算法day06 双指针 80. 合并两个有序数组
• C# 方法中的参数数组
• 吴师兄学算法day06 双指针 26. 删除有序数组中的重复项
• 打印稀疏数组
• 吴师兄学算法day06 双指针 88. 合并两个有序数组

油漆匠 油漆 下标 整数 数组油漆匠 油漆 下标 整数 油漆 油漆匠 墙壁 油漆 蓝桥 题解 油漆 面积 下标pairs整数 数组 数组 下标 整数 蓝桥 油漆 面积p8648 下标 整数 数组 长度 下标 整数 数组 数目