265 Paint House II
265. Paint House II
题目: https://leetcode.com/problems/paint-house-ii/
难度:
Hard
思路：
感觉不像hard 题，知道为啥hard了，因为can you solve it in O(nk) runtime
数组 dp[x][k] 代表第x个房子paint 0..k的值
用paint house 1 改的AC代码：
不过这个时间复杂度是O(nkk)吧
class Solution(object):
def minCostII(self, costs):
"""
:type costs: List[List[int]]
:rtype: int
"""
n = len(costs)
if n == 0 : return 0
elif n == 1 : return min (costs[0])
else:
k = len(costs[0]) if n else 0
dp = [[0 for i in range(k)] for j in range(n)]
dp[0] = costs[0]
for i in range(1,n):
for j in range(0,k):
minVal = float('inf')
for m in range(0,k):
if m != j and dp[i-1][m] < minVal:
minVal = dp[i-1][m]
dp[i][j] = minVal + costs[i][j]
return min(dp[-1])
