动态规划
class Solution:
def minCost(self, costs):
row, col = len(costs), 3
dp = [[0] * col for _ in range(row + 1)]
for i in range(1, row + 1):
for j in range(col):
dp[i][j] = costs[i - 1][j - 1]
if j == 0:
dp[i][j] += min(dp[i - 1][1], dp[i - 1][2])
elif j == 1:
dp[i][j] += min(dp[i - 1][0], dp[i - 1][2])
elif j == 2:
dp[i][j] += min(dp[i - 1][0], dp[i - 1][1])
return min(dp[row])
dp[i][j]:
i表示第i个房子,j表示涂成的颜色(0、1、2分别表示涂成红、蓝、绿色),dp[i][j]表示第i个房子涂成j色需要的最少成本(只要不和第i-1个房子颜色相同)