256. Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

 

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = []
Output: 0

Example 3:

Input: costs = [[7,6,2]]
Output: 2

 

Constraints:

  • costs.length == n
  • costs[i].length == 3
  • 0 <= n <= 100
  • 1 <= costs[i][j] <= 20

Rust Solution

struct Solution;

impl Solution {
    fn min_cost(costs: Vec<Vec<i32>>) -> i32 {
        let n = costs.len();
        if n == 0 {
            return 0;
        }
        let mut r = costs[0][0];
        let mut g = costs[0][1];
        let mut b = costs[0][2];
        for i in 1..n {
            let rr = i32::min(g, b) + costs[i][0];
            let gg = i32::min(r, b) + costs[i][1];
            let bb = i32::min(r, g) + costs[i][2];
            r = rr;
            g = gg;
            b = bb;
        }
        let mut res: Vec<i32> = [r, g, b].to_vec();
        res.sort_unstable();
        res[0]
    }
}

#[test]
fn test() {
    let costs: Vec<Vec<i32>> = vec_vec_i32![[17, 2, 17], [16, 16, 5], [14, 3, 19]];
    assert_eq!(Solution::min_cost(costs), 10);
}

Having problems with this solution? Click here to submit an issue on github.