265. Paint House II

一道dp的题目，主要是要找出状态和转移方程。但是怎么去找状态或者怎么去找转移方程还是很考验做题熟练度的，好像也没什么其他好的办法。

class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if not costs:
            return 0
        # dp[i][j] # paint 0 ~ ith house with the ending color j the minimum cost is dp[i][j]
        m = len(costs)
        n = len(costs[0])
        dp = [[sys.maxint for _ in range(n)] for _ in range(m)]
        for j in range(n):
            dp[0][j] = costs[0][j]
        
        for i in range(1, m):
            for j in range(n):
                for k in range(n):
                    if k != j:
                        dp[i][j] = min(dp[i][j], dp[i-1][k] + costs[i][j])
        res = sys.maxint
        for j in range(n):
            res = min(res, dp[m-1][j])
        
        return res