yangq's blog

观心中月,破心中贼

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. 带不同状态的动态规划

参考