2020-2-21 刷题记录

0X00 leetcode 做了 1 道

• 256. Paint House

0X01 每道题的小小总结

今天上了一节「动态规划」的课,感觉收获还是很大的,明天先把今天拉的题目补上

今天上午的时候有点浮躁,整个人静不下来,下午主要去写容器相关的代码了

这个题不仅和 cost 有关还和上一次的状态相关,和一般的动态规划有点不一样

256. Paint House

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        if len(costs) == 0: return 0
        record = [[costs[0][0], costs[0][1], costs[0][2]], [0, 0, 0]]
        new, old = 0, 1

        for i in range(1, len(costs)):
            if i == 0: continue
            new, old = old, new
            for color in range(3):
                record[new][color] = float("inf")
                for lastColor in range(3):
                    if color == lastColor: continue
                    cost = record[old][lastColor] + costs[i][color]
                    if cost < record[new][color]:
                        record[new][color] = cost
        
        return min(record[new])