265. Paint House II && 256. Paint House
问题
256题是说，有一排房子，每个房子可以染三种颜色， 每个房子染每种颜色都有一个价格，问最少需要花多少钱
限制是两个相同的颜色不能连着。
解析
这个题目一开始想的简单了，单纯没看到限制，以为是每个房子的染色最低价格相加即可。
之后发现限制后，想了一下每个你在染完所有房子之前没办法知道他的最便宜的价格，来源于哪种组合（每个房子染什么颜色）。所以只能是从第一栋开始，染所有色的价格依次累加，到第二栋，你只有把所有可以刷的颜色的价格都算一遍，才能知道刷到当前这个房子，最便宜的是哪种方法。
看到这里，又是当前的结果来源于前面的问题。动态规划走起。（现在联系一下，这个题目被一些解析归纳为网格问题确实是。网格是向右向下走，再加上向斜下方走）这个每次走其实也是有2种选择， 除了当前颜色的另外两种颜色。
这个地方状态的定义来源于结果，即当前房子的最低价格，dp[n]，但是没法看到截止到之前房子刷某种颜色后总共要花多少钱，所以还要再加一个状态就是当前的房子刷了什么颜色。dp[n][k]。在256题里这个k是3，在第265题中其实就是将这个数字一般化了。两个题代码是一样的套路。
初始化依然是所有数值先置为最大值，第一栋房子不需要考虑前面的，所以截止到他，染每种颜色的价格就是他本身的价格。
状态转移公式可以根据上文的解析，得出:
if (x != j) {
sums[i][j] = Math.min(sums[i][j], sums[i-1][x] + costs[i][j]);
}
在当前的颜色不等于前一个的颜色的情况下，都可以选择。遍历所有的可能。
代码
265
class Solution {
public int minCostII(int[][] costs) {
int n = costs.length;
int k = costs[0].length;
int[][] sums = new int[n][k];
for (int[] sum : sums) {
Arrays.fill(sum, Integer.MAX_VALUE);
}
for (int i = 0; i < k; i++) {
sums[0][i] = costs[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) {
if (x != j) {
sums[i][j] = Math.min(sums[i][j], sums[i-1][x] + costs[i][j]);
}
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
res = Math.min(res, sums[n-1][i]);
}
return res;
}
}
256
这个题目因为k=3， 直接展开也可以，我就展开写了。
class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) return Integer.MAX_VALUE;
int m = costs.length;
int[][] sums = new int[m][3];
sums[0][0] = costs[0][0];
sums[0][1] = costs[0][1];
sums[0][2] = costs[0][2];
for (int i = 1; i < m; i++) {
sums[i][0] = Math.min(sums[i-1][1], sums[i-1][2]) + costs[i][0];
sums[i][1] = Math.min(sums[i-1][0], sums[i-1][2]) + costs[i][1];
sums[i][2] = Math.min(sums[i-1][1], sums[i-1][0]) + costs[i][2];
}
return Math.min(sums[m-1][0], Math.min(sums[m-1][1], sums[m-1][2]));
}
}
- Paint House II && 256.
Question
Question 256 says that there is a row of houses, each house can be painted in three colors, each house has a price for each color, and asks how much it costs at least
The restriction is that two of the same color cannot be in a row.
Analysis
At first, I thought it was a simple question, because I didn't see the limit and thought that the minimum price for each house could be added up.
After I found the limit, I thought about how there is no way to know the cheapest price of each house before you dye all of them, from which combination (what color each house is dyed). So you can only start from the first house, dyeing all the colors in order to add up the price, to the second house, you can only count the price of all the colors that can be painted once, to know to paint to the current house, the cheapest is which method.
See here, again, the current result comes from the previous question. Dynamic planning goes on. (Now connect the dots, this topic is summarized by some parsing as a grid problem is indeed. The grid is to the right and down, plus to the bottom of the slope.) This walk is actually 2 choices each time, in addition to the current color of the other two colors.
The definition of the state of this place comes from the result, that is, the lowest price of the current house, dp[n], but there is no way to see how much the house will cost in total after painting a certain color up to the previous one, so there is another state that is what color the current house is painted. dp[n][k]. In question 256 this k is 3, in question 265 it is actually a generalization of this number. The code is the same routine for both questions.
The initialization is still all values first set to the maximum, the first house does not need to consider the previous, so as of him, the price of dyeing each color is his own price.
The state transfer formula can be derived from the parsing above :
if (x ! = j) {
sums[i][j] = Math.min(sums[i][j], sums[i-1][x] + costs[i][j]);
}
In all cases where the current color is not equal to the color of the previous one, selection is possible. Iterate through all possibilities.
Code
265
class Solution {
public int minCostII(int[][] costs) {
int n = costs.length;
int k = costs[0].length;
int[][] sums = new int[n][k];
for (int[] sum : sums) {
Arrays.fill(sum, Integer.MAX_VALUE);
}
for (int i = 0; i < k; i++) {
sums[0][i] = costs[0][i];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) {
if (x ! = j) {
sums[i][j] = Math.min(sums[i][j], sums[i-1][x] + costs[i][j]);
}
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
res = Math.min(res, sums[n-1][i]);
}
return res;
}
}
256
I expanded this topic because k=3, so it's fine to expand it directly.
class Solution {
public int minCost(int[][] costs) {
if (costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) return Integer.MAX_VALUE;
int m = costs.length;
int[][] sums = new int[m][3];
sums[0][0] = costs[0][0];
sums[0][1] = costs[0][1];
sums[0][2] = costs[0][2];
for (int i = 1; i < m; i++) {
sums[i][0] = Math.min(sums[i-1][1], sums[i-1][2]) + costs[i][0];
sums[i][1] = Math.min(sums[i-1][0], sums[i-1][2]) + costs[i][1];
sums[i][2] = Math.min(sums[i-1][1], sums[i-1][0]) + costs[i][2];
}
return Math.min(sums[m-1][0], Math.min(sums[m-1][1], sums[m-1][2]));
}
}