256. Paint-House.md

Description

There are a row of n houses, each house can be painted with one of the 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 a *n* x *3* cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note: All costs are positive integers.

Example:

Input: [[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.

---

python solution

读完题，瞬间想到三角形数组中找到值最小的路径那道题。简直一模一样有没有。

以下面的输入maxtrix为例

[[17,2,17],
 [16,16,5],
 [14,3,19]]

• 一层一层的遍历，对于第二层matrix[1][0] = 16这个位置，最小花费是matrix[1][0] + min(matrix[0][1], matrix[0][2])，即第i层某元素的最小花费为（当前花费 + 上一层（i-1）两个不相邻元素的最小值）。一层一层的遍历，最终返回最底层的最小花费即可。

  class Solution:
      def minCost(self, costs):
          """
          :type costs: List[List[int]]
          :rtype: int
          """
          for i in range(1, len(costs)):
              costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])
              costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])
              costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])
          return min(costs[-1]) if len(costs) > 0 else 0