Leetcode 256.粉刷房子

Time: 20190903
Type: Easy

题目描述

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

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

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/paint-house
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题意我开始理解的都好费劲啊，给的这个输入[[17,2,17],[16,16,5],[14,3,19]]，我总是在想，第17号房子，第16号房子，第14号房子，三者不连续。。。

实际上，n个房子，是用顺序下标的含义来表示的，这三个房子，每个三元数组表示三种颜色对应的花费。

因为我自己卡在题意理解上了，那么我就多说几句。[17,2,17]表示0号房子刷三种颜色分别的花费。

定义状态f[i][j]表示第i号房子粉刷为颜色j的最小花费。

考虑第i套房子的花费时，需要考虑到第i-1套房子的消费，因为相邻的房子颜色不能相同。

每种房子可以选的颜色有三种，我们从第二栋房子开始建立状态转移表达式，考虑第二栋房子的时候，只需要看左边的房子颜色怎么选即可，如果当前房子选择颜色1，则左边的房子只能选择颜色0和2，那么f[i][0] = costs[i][0] + min(f[i-1][1], f[i-1][2])。
当前房子有三种颜色可选，f[i][1] = costs[i][1] + min(f[i-1][0], f[i-1][2])， f[i][2] = costs[i][2] + min(f[i-1][0], f[i-1][1]).

第三栋房子只需要看第二栋房子怎么选即可。这满足无后效性。

直接在costs数组上修改，省去了新开辟空间的麻烦，更新f数组的过程，恰好costs还能发挥应用的作用（提供涂当前颜色的成本）。

代码

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        if not costs:
            return 0
        f = costs
        for i in range(1, len(f)):
            f[i][0] += min(f[i-1][1], f[i-1][2])
            f[i][1] += min(f[i-1][0], f[i-1][2])
            f[i][2] += min(f[i-1][0], f[i-1][1])
        return min(f[-1])

参考

https://www.cnblogs.com/lightwindy/p/8476910.html

END.