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 == ncosts[i].length == 30 <= n <= 1001 <= costs[i][j] <= 20struct 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);
}