【The sword refers to Offer II 091. Paint the house】

剑指 Offer II 091. 粉刷房子

假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同.

当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的.每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的.

例如,costs[0][0] 表示第 0 号房子粉刷成红色的成本花费;costs[1][2] 表示第 1 号房子粉刷成绿色的花费,以此类推.

请计算出粉刷完所有房子最少的花费成本.

示例 1：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10

解释: 将 0 号房子粉刷成蓝色,1 号房子粉刷成绿色,2 号房子粉刷成蓝色.
最少花费: 2 + 5 + 3 = 10.

示例 2：

输入: costs = [[7,6,2]]
输出: 2

题解

动态规划
Each house can be painted in one of three colors,It is necessary to calculate the minimum cost of painting all the houses under the condition that the colors of the adjacent houses are different.As when known before painting ii the minimum cost of a house,According to Stucco pp$i+1$ No. The cost of the house can be calculated before painting $i+1$The minimum cost of a house,So the minimum cost can be calculated using dynamic programming.

Since each house can be painted in one of three colors,Therefore, the minimum cost of painting in three colors needs to be considered separately.

用 $\text{dp}[i][j]$ 表示粉刷第 0 号房子到第 i 号房子且第 i 号房子被粉刷成第 j 种颜色时的最小花费成本.由于一共有 n a house and 3 种颜色,因此 $0\le i<n$,$0\le j<3$.

when only the first 0 When the house was painted,对于每一种颜色,The total cost will be the first 0 The cost of painting a house in that color,So the boundary conditions are ：对于任意 $0\le j<3,\text{dp}[0][j]=\text{costs}[0][j]$.

对于 $1\le i<n$,第 i No. House and No i−1 No. House color must be different,因此当第 i When the house is painted in a certain color,第 i−1 House No. can only be painted in one of the other two colors.当第 i House No. was painted in three colors,粉刷第 0 号房子到第 i The minimum cost of house No. is calculated as follows：

$\begin{array}{rl}\text{dp}[i][0]& =\min (\text{dp}[i-1][1],\text{dp}[i-1][2])+\text{costs}[i][0]\\ \text{dp}[i][1]& =\min (\text{dp}[i-1][0],\text{dp}[i-1][2])+\text{costs}[i][1]\\ \text{dp}[i][2]& =\min (\text{dp}[i-1][0],\text{dp}[i-1][1])+\text{costs}[i][2]\end{array}$
​

The three color cases can be combined into one state transition equation,对于 $1\le i<n$ 和 $0\le j<3$,状态转移方程如下：

$$\text{dp}[i][j]=\min (\text{dp}[i-1][(j+1)\mathrm{m}\mathrm{o}\mathrm{d}3],$$
$$\text{dp}[i-1][(j+2)\mathrm{m}\mathrm{o}\mathrm{d}3])+\text{costs}[i][j]$$

计算结束时,$\text{dp}[n-1]$ The smallest of these is the minimum cost to paint all the houses.

当 $i\ge 1$ 时,由于 $\text{dp}[i]$的计算只和 $\text{dp}[i-1]$ 有关,So space can be optimized using rolling arrays,将空间复杂度降低到 $O(1)$.

代码

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        dp = costs[0]
        for i in range(1, len(costs)):
            dp = [min(dp[j - 1], dp[j - 2]) + c for j, c in enumerate(costs[i])]
        return min(dp)