265. 粉刷房子 II

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/paint-house-ii/
Star
假如有一排房子共有 n 幢，每个房子可以被粉刷成 k 种颜色中的一种。房子粉刷成不同颜色的花费成本也是不同的。你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
每个房子粉刷成不同颜色的花费以一个 n x k 的矩阵表示。
例如，costs[0][0] 表示第 0 幢房子粉刷成 0 号颜色的成本；costs[1][2] 表示第 1 幢房子粉刷成 2 号颜色的成本，以此类推。 返回 粉刷完所有房子的最低成本 。
示例 1：
输入: costs = [[1,5,3],[2,9,4]] 输出: 5 解释: 将房子 0 刷成 0 号颜色，房子 1 刷成 2 号颜色。花费: 1 + 4 = 5; 或者将 房子 0 刷成 2 号颜色，房子 1 刷成 0 号颜色。花费: 3 + 2 = 5. 示例 2:
输入: costs = [[1,3],[2,4]] 输出: 5

法1 动态规划 第一类基本型

思路
dp[i][j] 为 i 房子 涂为 颜色 j 所需要的花费。相邻的房子不能涂同样的色，所以要遍历前一所房子除j之外的所有颜色 + cost[i][j]。
题解
class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        n, k = len(costs), len(costs[0])
        dp = [[0]*k for _ in range(n)]
        dp[0] = costs[0]

        for i in range(1, len(dp)):
            for j in range(k):
                dp[i][j] = costs[i][j] + \
                            min([dp[i-1][c] for c in range(k) if c != j])

        return min(dp[-1])