dp系列之房屋染色

数据结构动态规划
dp系列, 数据结构, 高频面试题总结

房屋染色

这里有n个房子在一列直线上，现在我们需要给房屋染色，分别有红色蓝色和绿色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。
费用通过一个nx3 的矩阵给出，比如cost[0][0]表示房屋0染红色的费用，cost[1][2]表示房屋1染绿色的费用。

样例：
costs = [[14,2,11],[11,14,5],[14,3,10]] return 10
房屋 0 蓝色, 房屋 1 绿色, 房屋 2 蓝色， 2 + 5 + 3 = 10

思路：

  • 动态规划
  • 状态转移公式：costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2])

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    /**
     * @param costs n x 3 cost matrix
     * @return an integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        // Write your code here
        /**
         * 当决定当前房屋涂何种颜色时，也决定相邻房屋的可选颜色
         * 将所有可能性枚举，选择费用最小的
         * 
         * */
         
         if(costs == null || costs.length == 0) {
             return 0;
         }
         
         for(int i = 1; i < costs.length; i++) {
             costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
             costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
             costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
         }
         
         int minCost = Math.min(costs[costs.length - 1][0], costs[costs.length - 1][1]);
         minCost = Math.min(minCost, costs[costs.length - 1][2]);
         
         return minCost;
    }
}

房屋染色 II

这里有n个房子在一列直线上，现在我们需要给房屋染色，共有k种颜色。每个房屋染不同的颜色费用也不同，你需要设计一种染色方案使得相邻的房屋颜色不同，并且费用最小。

费用通过一个nxk 的矩阵给出，比如cost[0][0]表示房屋0染颜色0的费用，cost[1][2]表示房屋1染颜色2的费用。

样例：
costs = [[14,2,11],[11,14,5],[14,3,10]] return 10
房屋 0 颜色 1, 房屋 1 颜色 2, 房屋 2 颜色 1， 2 + 5 + 3 = 10

思路：

  • 把i中for函数里面加个for循环即可
  • 写个功能函数，算临近房屋涂其他颜色时候的最小值

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
    /**
     * @param costs: n x k cost matrix
     * @return: an integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // write your code here
        if (costs == null || costs.length == 0)
            return 0;
        for (int i = 1; i < costs.length; i++) {
            for (int j = 0; j < costs[0].length; j++) {
                costs[i][j] += helper(costs, i, j);
            }
            
        }
        //最后是求所有中最小的，这里用了个-1,可以算是小trick吧~
        return helper(costs, costs.length, -1);
                
    }
    
    private int helper(int[][] costs, int i, int j) {
        int min = Integer.MAX_VALUE;
        for (int k = 0; k < costs[0].length; k++) {
            if (k == j)
                continue;
            else if (min > costs[i-1][k])
                min = costs[i-1][k];
        }
        return min;
    }
}
Compartir Comentarios