Paint house iv

Array Dynamic Programming

45.1% acceptance

Feb 25, 2026

121

You are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cost of size n x 3, where cost[i][j] represents the cost of painting house i with color j + 1. The houses will look beautiful if they satisfy the following conditions: No two adjacent houses are painted the same color. Houses equidistant from the ends of the row are not painted the same color. For example, if n = 6, houses at positions (0, 5), (1, 4), and (2, 3) are considered equidistant. Return the minimum cost to paint the houses such that they look beautiful.

Solution

Rust

Time O(n * m)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost(n: i32, cost: Vec<Vec<i32>>) -> i64 {
    let n = n as usize;
    const INF: i64 = i64::MAX / 2;
    // dp[c1][c2] = min cost where house i has color c1, house n-1-i has color c2
    let mut dp = [[INF; 3]; 3];
    // Base: pair 0 (houses 0 and n-1)
    for c1 in 0..3 {
      for c2 in 0..3 {
        if c1 != c2 {
          dp[c1][c2] = cost[0][c1] as i64 + cost[n-1][c2] as i64;
        }
      }
    }
    // Pairs 1..n/2-1
    for p in 1..n/2 {
      let mut ndp = [[INF; 3]; 3];
      let li = p;
      let ri = n - 1 - p;
      for c1 in 0..3 {
        for c2 in 0..3 {
          if c1 == c2 { continue; }
          let add = cost[li][c1] as i64 + cost[ri][c2] as i64;
          for pc1 in 0..3 {
            if pc1 == c1 { continue; }
            for pc2 in 0..3 {
              if pc2 == c2 { continue; }
              if dp[pc1][pc2] == INF { continue; }
              let v = dp[pc1][pc2] + add;
              if v < ndp[c1][c2] { ndp[c1][c2] = v; }
            }
          }
        }
      }
      dp = ndp;
    }
    let mut ans = INF;
    for c1 in 0..3 { for c2 in 0..3 { if dp[c1][c2] < ans { ans = dp[c1][c2]; } } }
    ans
  }
}