Paint house iii

Array Dynamic Programming

61.2% acceptance

Feb 25, 2026

2130

156

There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that have been painted last summer should not be painted again. A neighborhood is a maximal group of continuous houses that are painted with the same color. Given an array houses, an m x n matrix cost and an integer target where: houses[i]: is the color of the house i, and 0 if the house is not painted yet. cost[i][j]: is the cost of paint the house i with the color j + 1. Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods. If it is not possible, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(houses: Vec<i32>, cost: Vec<Vec<i32>>, m: i32, n: i32, target: i32) -> i32 {
    let m = m as usize;
    let n = n as usize;
    let t = target as usize;
    const INF: i32 = i32::MAX / 2;
    // dp[color][neighborhoods] for current house (1-indexed colors, 1-indexed neighborhoods)
    let mut dp = vec![vec![INF; t + 1]; n + 1];
    // Initialize for house 0
    if houses[0] != 0 {
      dp[houses[0] as usize][1] = 0;
    } else {
      for c in 1..=n {
        dp[c][1] = cost[0][c - 1];
      }
    }
    for i in 1..m {
      let mut ndp = vec![vec![INF; t + 1]; n + 1];
      let colors: Vec<usize> = if houses[i] != 0 {
        vec![houses[i] as usize]
      } else {
        (1..=n).collect()
      };
      for &c in &colors {
        let paint_cost = if houses[i] != 0 { 0 } else { cost[i][c - 1] };
        for prev_c in 1..=n {
          for nt in 1..=t {
            if dp[prev_c][nt] == INF { continue; }
            let new_t = if prev_c == c { nt } else { nt + 1 };
            if new_t > t { continue; }
            let new_cost = dp[prev_c][nt] + paint_cost;
            if new_cost < ndp[c][new_t] {
              ndp[c][new_t] = new_cost;
            }
          }
        }
      }
      dp = ndp;
    }
    let ans = (1..=n).map(|c| dp[c][t]).min().unwrap_or(INF);
    if ans == INF { -1 } else { ans }
  }
}