0%

刷算法(16)-粉刷房子

256. 粉刷房子(会员题)

假如有一排房子,共 n 个,每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种,你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。当然,因为市场上不同颜色油漆的价格不同,所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的矩阵来表示的。

屏幕快照 2019-10-18 上午1.14.21.png

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
public int minCost(int[][] costs) {
int n = costs.length;
int[][] dp = new int[n][3];
dp[0][0] = costs[0][0];
dp[0][1] = costs[0][1];
dp[0][2] = costs[0][2];
for (int i = 1; i < n; i++){
for (int j = 0; j < 3; j++){
dp[i][j] = Math.min(dp[i-1][(j+1)%3], dp[i-1][(j+2)%3]) + costs[i][j];
}
}
return Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]);
}

思路

我们需要知道dp[i]和dp[i-1]之间的关系,设dp[i] 是粉刷到第i个房子要花费的最少成本。则dp[i]和第i个房子的状态有关,这样dp[i]有三种情况,分别刷对应的三种颜色。
屏幕快照 2019-10-18 上午1.18.56.png

心得

  1. 一定要处理输入数组为空的情况返回0;
  2. 带不同状态的动态规划

参考