LeetCode 256: Paint House (Rolling DP with 3 Colors)

2026-04-08 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 256DPRolling State

Today we solve LeetCode 256 - Paint House.

Source: https://leetcode.com/problems/paint-house/

LeetCode 256 paint house DP transition diagram across red blue green costs

English

Problem Summary

We have n houses in a row. Each house can be painted Red, Blue, or Green, and costs[i][c] gives the cost for house i with color c. Adjacent houses cannot share the same color. Return the minimum total cost.

Key Insight

For each house, choosing one color only depends on the best totals from the previous house with the other two colors. So we only need three rolling values: r, b, g.

DP Transition

newR = costs[i][0] + min(b, g)
newB = costs[i][1] + min(r, g)
newG = costs[i][2] + min(r, b)

Complexity Analysis

Time: O(n).
Space: O(1) extra space.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) return 0;

        int r = costs[0][0], b = costs[0][1], g = costs[0][2];
        for (int i = 1; i < costs.length; i++) {
            int newR = costs[i][0] + Math.min(b, g);
            int newB = costs[i][1] + Math.min(r, g);
            int newG = costs[i][2] + Math.min(r, b);
            r = newR;
            b = newB;
            g = newG;
        }
        return Math.min(r, Math.min(b, g));
    }
}

func minCost(costs [][]int) int {
    if len(costs) == 0 {
        return 0
    }

    r, b, g := costs[0][0], costs[0][1], costs[0][2]
    for i := 1; i < len(costs); i++ {
        newR := costs[i][0] + min(b, g)
        newB := costs[i][1] + min(r, g)
        newG := costs[i][2] + min(r, b)
        r, b, g = newR, newB, newG
    }
    return min(r, min(b, g))
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;

        int r = costs[0][0], b = costs[0][1], g = costs[0][2];
        for (int i = 1; i < (int)costs.size(); ++i) {
            int newR = costs[i][0] + min(b, g);
            int newB = costs[i][1] + min(r, g);
            int newG = costs[i][2] + min(r, b);
            r = newR;
            b = newB;
            g = newG;
        }
        return min(r, min(b, g));
    }
};

class Solution:
    def minCost(self, costs):
        if not costs:
            return 0

        r, b, g = costs[0]
        for i in range(1, len(costs)):
            nr = costs[i][0] + min(b, g)
            nb = costs[i][1] + min(r, g)
            ng = costs[i][2] + min(r, b)
            r, b, g = nr, nb, ng

        return min(r, b, g)

var minCost = function(costs) {
  if (!costs || costs.length === 0) return 0;

  let [r, b, g] = costs[0];
  for (let i = 1; i < costs.length; i++) {
    const newR = costs[i][0] + Math.min(b, g);
    const newB = costs[i][1] + Math.min(r, g);
    const newG = costs[i][2] + Math.min(r, b);
    r = newR;
    b = newB;
    g = newG;
  }
  return Math.min(r, b, g);
};

中文

题目概述

有 n 间房子排成一排，每间房可刷红/蓝/绿三种颜色，costs[i][c] 表示第 i 间刷某色的成本。相邻房子不能同色，求最小总成本。

核心思路

第 i 间选择某种颜色时，只依赖第 i-1 间另外两种颜色的最优成本。因此状态可以压缩为三个滚动变量：r、b、g。

状态转移