### 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])
```