粉刷房子

难度: Medium

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

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

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

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

示例 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

提示:

costs.length == n
costs[i].length == 3
1 <= n <= 100
1 <= costs[i][j] <= 20

注意：本题与主站 256 题相同：https://leetcode-cn.com/problems/paint-house/

Submission

运行时间: 21 ms

内存: 16.0 MB

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        red, blue, green = 0, 0, 0
        for r, b, g in costs:
            red, blue, green = min(blue, green) + r, min(red, green) + b, min(red, blue) + g
        return min(red, blue, green)

Explain

此题解采用动态规划的方法来解决粉刷房子的问题。定义三个变量red, blue, green来分别表示粉刷到当前房子时，若当前房子粉刷为红色、蓝色和绿色的最小花费。对于每个房子，我们根据前一个房子的颜色花费来更新这三个变量。例如，如果当前房子选择粉刷为红色，则前一个房子只能是蓝色或绿色，因此当前的红色花费为前一个房子的蓝色和绿色花费的较小者加上当前房子粉刷为红色的花费。同理可得蓝色和绿色的更新公式。这个过程从第一个房子遍历到最后一个房子，最后从三个颜色花费中选择最小的即为结果。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        red, blue, green = 0, 0, 0  # 初始化每种颜色的起始花费为0
        for r, b, g in costs:  # 遍历每个房子的粉刷成本
            red, blue, green = min(blue, green) + r, min(red, green) + b, min(red, blue) + g  # 动态更新每种颜色的最小花费
        return min(red, blue, green)  # 返回三种颜色中的最小花费

Explore

在动态规划解决方案中，每次更新红色、蓝色和绿色花费的状态时，都是基于前一个房子的不同颜色的花费来计算的。例如，如果当前房子选择粉刷为红色，则它的花费是基于前一个房子粉刷为蓝色或绿色的最小花费加上当前房子粉刷红色的成本。这样的状态转移保证了每个房子的颜色与相邻房子的颜色不同。最终，我们从最后一个房子的三种颜色花费中选择最小值，这个值反映了遵循颜色不同规则的最小成本方案。

题解的动态规划方法主要关注于计算最小成本，而不是记录具体的粉刷方案。尽管存在可能有多种不同的粉刷方案达到相同的最小成本，但此方法只计算最小成本的值本身。如果需要获取所有可能的最小成本粉刷方案，需要对算法进行扩展，例如使用回溯法或保存所有最优路径的额外数据结构。

使用三个变量（red, blue, green）来存储状态而不使用数组的主要原因是空间效率和简洁性。每次计算只依赖于前一次的三个状态值，因此，只需要三个变量即可进行状态的更新，无需维护一个更大的数组来存储每个房子的颜色状态。这样做降低了空间复杂度，使算法更为高效而简洁。