动态规划
当前粉刷房子的花费可以由上一家粉刷房子的花费推导出来，所以可以使用动态规划求解这道题。
首先确定dp数组的含义，每个房子都可以被粉刷成三种颜色，那么自然而然可以得到数组
dp[i][j]
粉刷到第i个房子j颜色一共花的钱，i表示房子的数目，j表示颜色的种类。
初始化数组，就是第0间房子各种颜色的花费。
递推公式：dp[i][0] = costs[i][0] + Math.min(dp[i – 1][1], dp[i – 1][2]);
当前房子颜色为j时总花费 = 当前房子颜色为j时的花费 + 上一个房子颜色不为j（另外两种颜色）时的总花费的最小值
结果为最后一间房子三种颜色的最小值。
代码如下：
class Solution {
public int minCost(int[][] costs) {
int len = costs.length;
int[][] dp = new int[len][3];
for (int i = 0; i < 3; i++) {
dp[0][i] = costs[0][i];
}
for (int i = 1; i < len;i++) {
dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = costs[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
return Math.min(dp[len - 1][0], Math.min(dp[len - 1][1], dp[len - 1][2]));
}
}
由于当前状态完全由上一状态确定，所以可以使用滚动数组压缩状态，将空间复杂度降为1。
优化如下：
class Solution {
public int minCost(int[][] costs) {
int len = costs.length;
int[][] dp = new int[2][3];
for (int i = 0; i < 3; i++) {
dp[0][i] = costs[0][i];
}
for (int i = 1; i < costs.length;i++) {
dp[1][0] = costs[i][0] + Math.min(dp[0][1], dp[0][2]);
dp[1][1] = costs[i][1] + Math.min(dp[0][0], dp[0][2]);
dp[1][2] = costs[i][2] + Math.min(dp[0][0], dp[0][1]);
for (int j = 0; j < 3; j++) {
dp[0][j] = dp[1][j];
}
}
return len == 1 ? Math.min(dp[0][0], Math.min(dp[0][1], dp[0][2])) : Math.min(dp[1][0], Math.min(dp[1][1], dp[1][2]));
}
}
原文：https://leetcode.cn/problems/JEj789/solution/jian-dan-dp-by-nice-hermann9a2-81ol/
Original: https://www.cnblogs.com/liangren-na/p/16437713.html
Author: 良人呐
Title: 剑指 Offer II 091. 粉刷房子
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/622206/
转载文章受原作者版权保护。转载请注明原作者出处！