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
