[Leetcode] Paint House 房子涂色

SunZhaopeng 发布于2019-08-14 12:46 / 1288人阅读

摘要：动态规划复杂度时间空间思路直到房子，其最小的涂色开销是直到房子的最小涂色开销，加上房子本身的涂色开销。我们在原数组上修改，可以做到不用空间。代码找出最小和次小的，最小的要记录下标，方便下一轮判断

Paint House

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs0 is the cost of painting house 0 with color red; costs1 is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note: All costs are positive integers.

动态规划 复杂度

时间 O(N) 空间 O(1)

思路

直到房子i，其最小的涂色开销是直到房子i-1的最小涂色开销，加上房子i本身的涂色开销。但是房子i的涂色方式需要根据房子i-1的涂色方式来确定，所以我们对房子i-1要记录涂三种颜色分别不同的开销，这样房子i在涂色的时候，我们就知道三种颜色各自的最小开销是多少了。我们在原数组上修改，可以做到不用空间。

代码

public class Solution {
    public int minCost(int[][] costs) {
        if(costs != null && costs.length == 0) return 0;
        for(int i = 1; i < costs.length; i++){
            // 涂第一种颜色的话，上一个房子就不能涂第一种颜色，这样我们要在上一个房子的第二和第三个颜色的最小开销中找最小的那个加上
            costs[i][0] = costs[i][0] + Math.min(costs[i - 1][1], costs[i - 1][2]);
            // 涂第二或者第三种颜色同理
            costs[i][1] = costs[i][1] + Math.min(costs[i - 1][0], costs[i - 1][2]);
            costs[i][2] = costs[i][2] + Math.min(costs[i - 1][0], costs[i - 1][1]);
        }
        // 返回涂三种颜色中开销最小的那个
        return Math.min(costs[costs.length - 1][0], Math.min(costs[costs.length - 1][1], costs[costs.length - 1][2]));
    }
}

Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs0 is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note: All costs are positive integers.

Follow up: Could you solve it in O(nk) runtime?

动态规划 复杂度

时间 O(N) 空间 O(1)

思路

和I的思路一样，不过这里我们有K个颜色，不能简单的用Math.min方法了。如果遍历一遍颜色数组就找出除了自身外最小的颜色呢？我们只要把最小和次小的都记录下来就行了，这样如果和最小的是一个颜色，就加上次小的开销，反之，则加上最小的开销。

代码

public class Solution {
    public int minCostII(int[][] costs) {
        if(costs != null && costs.length == 0) return 0;
        int prevMin = 0, prevSec = 0, prevIdx = -1;
        for(int i = 0; i < costs.length; i++){
            int currMin = Integer.MAX_VALUE, currSec = Integer.MAX_VALUE, currIdx = -1;
            for(int j = 0; j < costs[0].length; j++){
                costs[i][j] = costs[i][j] + (prevIdx == j ? prevSec : prevMin);
                // 找出最小和次小的，最小的要记录下标，方便下一轮判断
                if(costs[i][j] < currMin){
                    currSec = currMin;
                    currMin = costs[i][j];
                    currIdx = j;
                } else if (costs[i][j] < currSec){
                    currSec = costs[i][j];
                }
            }
            prevMin = currMin;
            prevSec = currSec;
            prevIdx = currIdx;
        }
        return prevMin;
    }
}

GPU云服务器云服务器 House Paint LeetCode wm paint

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64696.html

[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原数组上动规，每一行对应一个房子，每一个元素代表从第一行的房子到这一行的房子选择这一种颜色所花的最小开销。所以每个元素该元素的值上一行两个与该元素不同列元素的值的较小者。不过这次要记录三个变量本行最小值，本行第二小值，本行最小值下标。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 评论0 收藏0
[Leetcode] Paint Fence 栅栏涂色

摘要：假设是第一根柱子及之前涂色的可能性数量，是第二根柱子及之前涂色的可能性数量，则。递推式有了，下面再讨论下情况，所有柱子中第一根涂色的方式有中，第二根涂色的方式则是，因为第二根柱子可以和第一根一样。 Paint Fence There is a fence with n posts, each post can be painted with one of the k colors. ...

sixleaves 2019-08-14 12:36 评论0 收藏0
leetcode 198 House Robber

摘要：但是任何临近的两个房子被偷就会触发警报。要求我们求出在不触发警报的情况下偷到的最多的钱。每个房子里的钱通过输入的数组表示。题目详情 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only...

jzman 2019-08-16 11:06 评论0 收藏0
LeetCode 337. House Robber III

摘要：一番侦察之后，聪明的小偷意识到这个地方的所有房屋的排列类似于一棵二叉树。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。 Description The thief has found himself a new place for his thievery again. There is only one entranc...

ymyang 2019-07-31 10:16 评论0 收藏0
leetcode198,213 house robber

摘要：你不能连着偷两家因为这样会触发警报系统。现在有一个数组存放着每一家中的可偷金额，问可以偷的最大金额为多少这里考验了动态编程的思想。动态编程要求我们将问题一般化，然后再找到初始情况开始这个由一般到特殊的计算过程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

whidy 2019-08-16 11:01 评论0 收藏0