目录
题目要求
思路：DP
- 三个颜色分开计算：
- 从头开始，假设第二栋房子颜色固定（设为red），那么第一栋房子就取blue和green中成本较小的一个；
- 将基于上述规则的三种颜色选择结果记录下来用于DP；
- 假设第三栋房子颜色固定（设为red），那么第二栋房子就为blue或green，那么在上一步的结果中选择较小的一个；
- 继续更新结果并依此类推；
- 最终在三种颜色的推理结果中选出最小的。
Java
class Solution {
public int minCost(int[][] costs) {
int r = costs[0][0], b = costs[0][1], g = costs[0][2];
for (int i = 1; i < costs.length; i++) {
int nr = Math.min(b, g) + costs[i][0];
int nb = Math.min(r, g) + costs[i][1];
int ng = Math.min(r, b) + costs[i][2];
r = nr;
b = nb;
g = ng;
}
return Math.min(r, Math.min(b, g));
}
}
- 时间复杂度：
O
(
3
n
)
O(3n)
O(3n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
C++
class Solution {
public:
int minCost(vector>& costs) {
int r = costs[0][0], b = costs[0][1], g = costs[0][2];
for (int i = 1; i < costs.size(); i++) {
int nr = min(b, g) + costs[i][0];
int nb = min(r, g) + costs[i][1];
int ng = min(r, b) + costs[i][2];
r = nr;
b = nb;
g = ng;
}
return min(r, min(b, g));
}
};
- 时间复杂度：
O
(
3
n
)
O(3n)
O(3n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
Rust
impl Solution {
pub fn min_cost(costs: Vec>) -> i32 {
let (mut r, mut b, mut g) = (costs[0][0], costs[0][1], costs[0][2]);
for i in 1..costs.len() {
let nr = b.min(g) + costs[i][0];
let nb = r.min(g) + costs[i][1];
let ng = r.min(b) + costs[i][2];
r = nr;
b = nb;
g = ng;
}
r.min(b.min(g))
}
}
- 时间复杂度：
O
(
3
n
)
O(3n)
O(3n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
一行解决版
- 思路是一样的，只不过用了数组的遍历函数into_iter()
impl Solution {
pub fn min_cost(costs: Vec>) -> i32 {
*costs.into_iter().fold([0, 0, 0], |rbg, cur| [cur[0] + rbg[1].min(rbg[2]), cur[1] + rbg[0].min(rbg[2]), cur[2] + rbg[0].min(rbg[1])]).iter().min().unwrap()
}
}
总结
常有的DP思维，下一栋房子的颜色只和上一栋有关就很ez。
