[Leetcode] Paint House 房子涂色

SunZhaopeng 發布于2019-08-14 12:46 / 1371人閱讀

摘要：動態規劃復雜度時間空間思路直到房子，其最小的涂色開銷是直到房子的最小涂色開銷，加上房子本身的涂色開銷。我們在原數組上修改，可以做到不用空間。代碼找出最小和次小的，最小的要記錄下標，方便下一輪判斷

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;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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