LeetCode 256. 粉刷房子

Categories:

题目描述
思路分析
1. 解法一：滚动 DP（推荐）
相似题目

题目描述

✅ 256. 粉刷房子

思路分析

解法一：滚动 DP（推荐）

核心思路：

dp[c] 表示刷到当前房子，且颜色为 c 的最小成本。

当前位置只能由前一房子的另外两种颜色转移而来。

每次迭代更新 dp，实现 O(1) 额外空间。

复杂度分析：

时间复杂度：O(n)，其中 n 表示房子数量。

空间复杂度：O(1)，仅使用常数额外空间。

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

        int[] dp = new int[3];
        dp[0] = costs[0][0];
        dp[1] = costs[0][1];
        dp[2] = costs[0][2];

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

            dp[0] = r;
            dp[1] = g;
            dp[2] = b;
        }

        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }
}

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

	dp := make([]int, 3)
	dp[0], dp[1], dp[2] = costs[0][0], costs[0][1], costs[0][2]

	for i := 1; i < len(costs); i++ {
		r := costs[i][0] + min(dp[1], dp[2])
		g := costs[i][1] + min(dp[0], dp[2])
		b := costs[i][2] + min(dp[0], dp[1])

		dp[0], dp[1], dp[2] = r, g, b
	}

	return min(dp[0], min(dp[1], dp[2]))
}

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

相似题目

题目	难度	考察点
265. 粉刷房子 II	困难	动态规划
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划
740. 删除并获得点数	中等	动态规划
120. 三角形最小路径和	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/35005026