一、 题目
1. 题目描述
剑指 Offer II 091. 粉刷房子
难度：中等
假如有一排房子，共 <code>n</code> 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 <code>n x 3</code><em> </em>的正整数矩阵 <code>costs</code> 来表示的。
例如，<code>costs[0][0]</code> 表示第 0 号房子粉刷成红色的成本花费；<code>costs[1][2]</code> 表示第 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
提示:
- <code>costs.length == n</code>
- <code>costs[i].length == 3</code>
- <code>1 <= n <= 100</code>
- <code>1 <= costs[i][j] <= 20</code>
注意：本题与主站 256 题相同：<a href="https://leetcode-cn.com/problems/paint-house/">https://leetcode-cn.com/problems/paint-house/</a>
2. 原题链接
二、 解题报告
1. 思路分析
比较简单的DP。
- 我们令dp[i]j 为第i个房子分别刷三种颜色时，前i个房子的总花费。显然答案就是min(dp[n-1])。
- 那么，当第i个房子刷颜色0，那么第i-1个房子只能刷颜色1,2，我们从中找小的那个选择，再计算i房子的花费即可；当i刷颜色1，i-1只能刷颜色0,2；i刷颜色2，i-1刷0，1
- 状态转移方程就很明显了：
- dp[i][0] = costs[i][0] + min(dp[i-1][1],dp[i-1][1])
- dp[i][1] = costs[i][1] + min(dp[i-1][0],dp[i-1][2])
- dp[i][2] = costs[i][2] + min(dp[i-1][1],dp[i-1][0])
- 讨论边界：
第0个房子显然没有限制，那么dp[0]=cost[0]
2. 复杂度分析
最坏时间复杂度O(n)
3. 代码实现
dp。
class Solution:
def minCost(self, costs: List[List[int]]) -> int:
n = len(costs)
dp = [[0]*3 for _ in range(n)]
dp[0] = costs[0]
for i in range(1,n):
dp[i][0] = costs[i][0] + min(dp[i-1][1],dp[i-1][2])
dp[i][1] = costs[i][1] + min(dp[i-1][0],dp[i-1][2])
dp[i][2] = costs[i][2] + min(dp[i-1][1],dp[i-1][0])
return min(dp[n-1])
三、 本题小结
- 设计好状态转移即可。
人生苦短，我用Python！
