<div>
There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.
The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs.
- For example,
costs[0][0]is the cost of painting house0with the color red;costs[1][2]is the cost of painting house 1 with color green, and so on...
Return the minimum cost to paint all houses.
Example 1:
<pre>Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10. </pre>
Example 2:
<pre>Input: costs = [[7,6,2]] Output: 2 </pre>
Constraints:
costs.length == ncosts[i].length == 31 <= n <= 1001 <= costs[i][j] <= 20
</div>
题目大意：
排屋相邻不同色地涂色(3色)的最低成本
解题思路：
低频题。最值且涉及数值考虑用DP。由于相邻不能同色，所以是多状态DP，有3个状态，不妨多用一维表示，第二维只有3值。
dp[i][j]定义为第i间屋涂上第j色的最低总费用，递归式为
1
dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])
解题步骤：
N/A
注意事项：
- 递归5步曲，多1，初始，多1，少1，答案。记得第一步初始化数组多1
Python代码：
1
2
3
4
5
6
7# dp[i][j] = min(dp[i-1][(j+1)%3] + costs[i-1][j], dp[i-1][(j+2)%3] + costs[i-1][j])
def minCost(self, costs: List[List[int]]) -> int:
dp = [[0] * 3 for _ in range(len(costs) + 1)]
for i in range(1, len(dp)):
for j in range(3):
dp[i][j] = min(dp[i - 1][(j + 1) % 3] + costs[i - 1][j], dp[i - 1][(j + 2) % 3] + costs[i - 1][j])
return min(dp[-1][0], dp[-1][1], dp[-1][2])
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
