力扣 256. 粉刷房子 LCR 091. 粉刷房子 python AC

动态规划

class Solution:def minCost(self, costs):row, col = len(costs), 3dp = [[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个房子颜色相同）