房屋染色

LeetCode题目地址
这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。

费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用

转移方程

转移方程

def minCost(self, costs):
        # write your code here
        #转移方程 f[i][0] = min(f[i-1][1],f[i-1][2])+cost[i][0]
        
        # 三个for循环的解释
        # i:第几个房子,等号左边和右边第一个参数
        # j:哪个颜色,等号左边第一个参数
        # k:哪个颜色,,等号右边边第二个参数
        
        #len(costs) 是行，len(costs[0])是列
        if len(costs) == 0 or len(costs[0]) == 0:
            return 0
        
        m = len(costs) 
        n = 3
        f = [[0 for i in range(n)] for i in range(m)]
        #初始化条件
        for i in range(n):
            f[0][i] = costs[0][i]
        
        #转移方程
        for i in range(1,m):
            for j in range(n):
                f[i][j] = float('inf')
                for k in range(n):
                   if j == k:
                       continue
                   f[i][j] = min(f[i-1][k]+costs[i][j],f[i][j])
                   
        return min(f[m-1][0],f[m-1][1],f[m-1][2])