题目要求

思路：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));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度：$O(3n)$
• 空间复杂度：$O(1)$

C++

class Solution {
public:
    int minCost(vector<vector<int>>& 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));
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度：$O(3n)$
• 空间复杂度：$O(1)$

Rust

impl Solution {
    pub fn min_cost(costs: Vec<Vec<i32>>) -> 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))
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 时间复杂度：$O(3n)$
• 空间复杂度：$O(1)$

一行解决版

• 思路是一样的，只不过用了数组的遍历函数into_iter()

impl Solution {
    pub fn min_cost(costs: Vec<Vec<i32>>) -> 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()
    }
}
1
2
3
4
5

总结

常有的DP思维，下一栋房子的颜色只和上一栋有关就很ez。