---

0256. 粉刷房子

• 标签：数组、动态规划
• 难度：中等

题目链接

• 0256. 粉刷房子 - 力扣

题目大意

描述：

假如有一排房子，共 $n$ 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 $n \times 3$ 的正整数矩阵 $costs$ 来表示的。

例如，$costs[0][0]$ 表示第 0 号房子粉刷成红色的成本花费；$costs[1]$[2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

要求：

请计算出粉刷完所有房子最少的花费成本。

说明：

• $costs.length == n$。
• $costs[i].length == 3$。
• $1 \le n \le 10^{3}$。
• $1 \le costs[i][j] \le 20$。

示例：

• 示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

• 示例 2：

输入: costs = [[7,6,2]]
输出: 2

解题思路

思路 1：动态规划

这是一个经典的动态规划问题。我们需要找到粉刷所有房子的最低成本，且相邻房子颜色不能相同。

核心思想是：

• 定义状态：$dp[i][j]$ 表示第 $i$ 个房子粉刷成第 $j$ 种颜色的最低成本，其中 $j \in \{0, 1, 2\}$ 分别代表红色、蓝色、绿色。
• 状态转移：$dp[i][j] = costs[i][j] + \min_{k \neq j} dp[i-1][k]$，即当前房子选择颜色 $j$ 的成本加上前一个房子选择其他颜色的最小成本。
• 最终答案：$\min(dp[n-1][0], dp[n-1][1], dp[n-1][2])$，即最后一个房子选择任意颜色的最小成本。

具体算法步骤：

1. 初始化：$dp[0][j] = costs[0][j]$，第一个房子选择任意颜色的成本就是对应的粉刷成本。
2. 状态转移：对于每个房子 $i$ 和每种颜色 $j$，计算 $dp[i][j] = costs[i][j] + \min(dp[i-1][k])$，其中 $k \neq j$。
3. 返回结果：$\min(dp[n-1][0], dp[n-1][1], dp[n-1][2])$。

思路 1：代码

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        # 处理空数组情况
        if not costs:
            return 0
        
        n = len(costs)
        
        # 如果只有一个房子，返回所有颜色中的最小成本
        if n == 1:
            return min(costs[0])
        
        # 初始化 dp 数组，dp[i][j] 表示第 i 个房子选择颜色 j 的最小成本
        dp = [[0] * 3 for _ in range(n)]
        
        # 初始化第一个房子的成本
        for j in range(3):
            dp[0][j] = costs[0][j]
        
        # 动态规划：计算每个房子选择每种颜色的最小成本
        for i in range(1, n):
            for j in range(3):
                # 当前房子选择颜色 j 的最小成本 = 当前颜色成本 + 前一个房子选择其他颜色的最小成本
                dp[i][j] = costs[i][j] + min(dp[i-1][k] for k in range(3) if k != j)
        
        # 返回最后一个房子选择任意颜色的最小成本
        return min(dp[n-1])

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是房子数量。需要遍历每个房子，每个房子计算 $3$ 种颜色的成本。
• 空间复杂度：$O(n)$，需要 $n \times 3$ 的 dp 数组存储状态。