class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
}
};
6447. 给墙壁刷油漆
给你两个长度为 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 <= 500cost.length == time.length1 <= cost[i] <= 1061 <= time[i] <= 500原站题解
javascript 解法, 执行用时: 120 ms, 内存消耗: 54.1 MB, 提交时间: 2024-06-28 07:44:10
/**
* @param {number[]} cost
* @param {number[]} time
* @return {number}
*/
var paintWalls = function(cost, time) {
let n = cost.length;
let f = new Array(n + 2).fill(Number.MAX_SAFE_INTEGER / 2);
f[0] = 0;
for (let i = 0; i < n; ++i) {
for (let j = n + 1; j >= 0; --j) {
f[Math.min(j + time[i], n) + 1] = Math.min(f[Math.min(j + time[i], n) + 1], f[j] + cost[i]);
}
}
return Math.min(f[n], f[n + 1]);
};
java 解法, 执行用时: 7 ms, 内存消耗: 42.7 MB, 提交时间: 2023-06-19 09:57:22
// 递推
class Solution {
public int paintWalls(int[] cost, int[] time) {
int n = cost.length;
var f = new int[n + 1];
Arrays.fill(f, Integer.MAX_VALUE / 2); // 防止加法溢出
f[0] = 0;
for (int i = 0; i < n; i++) {
int c = cost[i], t = time[i] + 1; // 注意这里加一了
for (int j = n; j > 0; j--)
f[j] = Math.min(f[j], f[Math.max(j - t, 0)] + c);
}
return f[n];
}
}
cpp 解法, 执行用时: 44 ms, 内存消耗: 86.5 MB, 提交时间: 2023-06-19 09:57:00
class Solution {
public:
int paintWalls(vector<int> &cost, vector<int> &time) {
int n = cost.size(), f[n + 1];
memset(f, 0x3f, sizeof(f));
f[0] = 0;
for (int i = 0; i < n; i++) {
int c = cost[i], t = time[i] + 1; // 注意这里加一了
for (int j = n; j; j--)
f[j] = min(f[j], f[max(j - t, 0)] + c);
}
return f[n];
}
};
golang 解法, 执行用时: 28 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-19 09:56:35
func paintWalls(cost, time []int) int {
n := len(cost)
f := make([]int, n+1)
for i := 1; i <= n; i++ {
f[i] = math.MaxInt / 2 // 防止加法溢出
}
for i, c := range cost {
t := time[i] + 1 // 注意这里加一了
for j := n; j > 0; j-- {
f[j] = min(f[j], f[max(j-t, 0)]+c)
}
}
return f[n]
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 72 ms, 内存消耗: 7.7 MB, 提交时间: 2023-06-19 09:56:21
// 0-1 背包
func paintWalls(cost, time []int) int {
n := len(cost)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int
dfs = func(i, j int) int { // j 表示剩余需要的体积
if j <= 0 { // 没有约束：后面什么也不用选了
return 0
}
if i < 0 { // 此时 j>0，但没有物品可选，不合法
return math.MaxInt / 2 // 防止加法溢出
}
p := &memo[i][j]
if *p != -1 {
return *p
}
*p = min(dfs(i-1, j-time[i]-1)+cost[i], dfs(i-1, j))
return *p
}
return dfs(n-1, n)
}
func min(a, b int) int { if b < a { return b }; return a }
golang 解法, 执行用时: 72 ms, 内存消耗: 7.9 MB, 提交时间: 2023-06-19 09:55:59
// dfs(i, j)
func paintWalls(cost, time []int) int {
n := len(cost)
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n*2+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dfs func(int, int) int
dfs = func(i, j int) int {
if j-n > i { // 注意 j 加上了偏移量 n
return 0 // 剩余的墙都可以免费刷
}
if i < 0 {
return math.MaxInt / 2 // 防止加法溢出
}
p := &memo[i][j]
if *p != -1 {
return *p
}
*p = min(dfs(i-1, j+time[i])+cost[i], dfs(i-1, j-1))
return *p
}
return dfs(n-1, n) // 加上偏移量 n，防止负数
}
func min(a, b int) int { if b < a { return b }; return a }
python3 解法, 执行用时: 1144 ms, 内存消耗: 16.3 MB, 提交时间: 2023-06-19 09:55:13
class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
n = len(cost)
f = [0] + [inf] * n # f[i][0] 表示 j<=0 的状态
for c, t in zip(cost, time):
for j in range(n, 0, -1):
f[j] = min(f[j], f[max(j - t - 1, 0)] + c)
return f[n]
python3 解法, 执行用时: 2528 ms, 内存消耗: 428.1 MB, 提交时间: 2023-06-19 09:55:00
'''
0-1背包问题，选或不选。
dfs(i, j) 考虑前i个物品，剩余还需凑出j的体积，此时最小价值和。
'''
class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
@cache # 记忆化搜索
def dfs(i: int, j: int) -> int: # j 表示剩余需要的体积
if j <= 0: return 0 # 没有约束：后面什么也不用选了
if i < 0: return inf # 此时 j>0，但没有物品可选，不合法
return min(dfs(i - 1, j - time[i] - 1) + cost[i], dfs(i - 1, j))
n = len(cost)
return dfs(n - 1, n)
python3 解法, 执行用时: 2424 ms, 内存消耗: 484.9 MB, 提交时间: 2023-06-19 09:52:57
'''
dfs(i, j), 刷前i堵墙，付费时间和减免费时间和为j的最小开销。
如果付费刷第i堵墙：dfs(i, j) = dfs(i-1, j+time[i]) + cost[i]
如果免费刷第i堵墙：dfs(i, j) = dfs(i-1, j-1)
两种情况取最小值。
'''
class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
@cache # 记忆化搜索
def dfs(i: int, j: int) -> int:
if j > i: return 0 # 剩余的墙都可以免费刷
if i < 0: return inf
return min(dfs(i - 1, j + time[i]) + cost[i], dfs(i - 1, j - 1))
return dfs(len(cost) - 1, 0)