LeetCode 256 Paint House

LeetCode

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 house 0 with 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:

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.

Example 2:

Input: costs = [[7,6,2]]
Output: 2

Constraints: costs.length == n
costs[i].length == 3 1 <= n <= 100
* 1 <= costs[i][j] <= 20

题目大意：

排屋相邻不同色地涂色(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代码：

# 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)