题目

题目来源：力扣（LeetCode）

假如有一排房子，共 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

思路分析

我们依次粉刷房子，而每次粉刷的颜色只跟上一间房子有关。如果当前房子想要刷红色，那么前一间房子只能是蓝色或者绿色，那么当前房子刷红色的最低花费就是 当前房子刷红色的成本 + Math.min(前一间房子刷蓝色的最低花费，前一间房子刷绿色的最低花费)。其余颜色以此类推。

定义 dp[i][j] ，表示如果第i个房子被涂了j色时(本质上就是三种颜色, 就以j=0,1,2代表)的最小花费
但这次涂了0色, 下次就只能涂1、2色，因此：
下一个房子粉刷颜色的最小花费为：dp[i+1][j] = costs[i+1][j] + min(dp[i]的其他两种可能)
如：dp[i+1][0] = costs[i+1][j] + min(dp[i][1], dp[i][2])
注意, dp[i][j]所描述的只是可能性, 需要在最后结果中取最小值

  1. /**
  2. * @param {number[][]} costs
  3. * @return {number}
  4. */
  5. // 思路：dp[i][j]表示当前第i个房子涂的第j个颜色 (本质上就是三种颜色, 就以j=0,1,2代表之)，当前的价格为之前房子dp[i-1][1]、dp[i-1]
  6. // [2]最小值 的价格加上当前costs[i][j]的价格，
  7. // 最后比较dp末尾三个元素，取最小值。
  8. var minCost = function (costs) {
  9.   let n = costs.length;
  10.   let dp = new Array(n);
  11.   for (let i = 0; i < dp.length; i++) dp[i] = new Array(3);
  12.   dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2];
  13.   for (let i = 1; i < n; i++) {
  14.     dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
  15.     dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
  16.     dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i][2];
  17.   }
  18.   return Math.min(Math.min(dp[dp.length - 1][0], dp[dp.length - 1][1]),
  19.     dp[dp.length - 1][2]);
  20. };