2020-2-21 刷题记录
2020-02-22 本文已影响0人
madao756
0X00 leetcode 做了 1 道
- 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])