Paint house

Array Dynamic Programming

64.3% acceptance

Mar 31, 2026

2383

134

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 an n x 3 cost matrix costs. 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... Return the minimum cost to paint all houses.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(costs: Vec<Vec<i32>>) -> i32 {
    let (mut r, mut g, mut b) = (0, 0, 0);
    for c in &costs {
      let (pr, pg, pb) = (r, g, b);
      r = c[0] + pg.min(pb);
      g = c[1] + pr.min(pb);
      b = c[2] + pr.min(pg);
    }
    r.min(g).min(b)
  }
}