代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你两个长度为 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 <= 500
cost.length == time.length
1 <= cost[i] <= 106
1 <= time[i] <= 500
我们可以考虑每一堵墙是给付费油漆匠刷还是给免费油漆匠刷,设计一个函数 $dfs(i, j)$,表示从第 $i$ 堵墙开始,且当前剩余的免费油漆匠工作时间为 $j$ 时,刷完剩余所有墙壁的最小开销。那么答案为 $dfs(0, 0)$。
函数 $dfs(i, j)$ 的计算过程如下:
注意,参数 $j$ 可能小于 $0$,因此,在实际编码过程中,除了 $Python$ 语言外,我们对 $j$ 加上一个偏移量 $n$,使得 $j$ 的取值范围为 $[0, 2n]$。
时间复杂度 $O(n^2)$,空间复杂度 $O(n^2)$。其中 $n$ 为数组长度。
class Solution:
def paintWalls(self, cost: List[int], time: List[int]) -> int:
@cache
def dfs(i: int, j: int) -> int:
if n - i <= j:
return 0
if i >= n:
return inf
return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1))
n = len(cost)
return dfs(0, 0)
class Solution {
private int n;
private int[] cost;
private int[] time;
private Integer[][] f;
public int paintWalls(int[] cost, int[] time) {
n = cost.length;
this.cost = cost;
this.time = time;
f = new Integer[n][n << 1 | 1];
return dfs(0, n);
}
private int dfs(int i, int j) {
if (n - i <= j - n) {
return 0;
}
if (i >= n) {
return 1 << 30;
}
if (f[i][j] == null) {
f[i][j] = Math.min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));
}
return f[i][j];
}
}
class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
int n = cost.size();
int f[n][n << 1 | 1];
memset(f, -1, sizeof(f));
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (n - i <= j - n) {
return 0;
}
if (i >= n) {
return 1 << 30;
}
if (f[i][j] == -1) {
f[i][j] = min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));
}
return f[i][j];
};
return dfs(0, n);
}
};
func paintWalls(cost []int, time []int) int {
n := len(cost)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n<<1|1)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if n-i <= j-n {
return 0
}
if i >= n {
return 1 << 30
}
if f[i][j] == -1 {
f[i][j] = min(dfs(i+1, j+time[i])+cost[i], dfs(i+1, j-1))
}
return f[i][j]
}
return dfs(0, n)
}
impl Solution {
#[allow(dead_code)]
pub fn paint_walls(cost: Vec<i32>, time: Vec<i32>) -> i32 {
let n = cost.len();
let mut record_vec: Vec<Vec<i32>> = vec![vec![-1; n << 1 | 1]; n];
Self::dfs(&mut record_vec, 0, n as i32, n as i32, &time, &cost)
}
#[allow(dead_code)]
fn dfs(
record_vec: &mut Vec<Vec<i32>>,
i: i32,
j: i32,
n: i32,
time: &Vec<i32>,
cost: &Vec<i32>
) -> i32 {
if n - i <= j - n {
// All the remaining walls can be printed at no cost
// Just return 0
return 0;
}
if i >= n {
// No way this case can be achieved
// Just return +INF
return 1 << 30;
}
if record_vec[i as usize][j as usize] == -1 {
// This record hasn't been written
record_vec[i as usize][j as usize] = std::cmp::min(
Self::dfs(record_vec, i + 1, j + time[i as usize], n, time, cost) +
cost[i as usize],
Self::dfs(record_vec, i + 1, j - 1, n, time, cost)
);
}
record_vec[i as usize][j as usize]
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。