成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Paint House 房子涂色

SunZhaopeng / 1373人閱讀

摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路直到房子，其最小的涂色開銷是直到房子的最小涂色開銷，加上房子本身的涂色開銷。我們?cè)谠瓟?shù)組上修改，可以做到不用空間。代碼找出最小和次小的，最小的要記錄下標(biāo)，方便下一輪判斷

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.
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

直到房子i，其最小的涂色開銷是直到房子i-1的最小涂色開銷，加上房子i本身的涂色開銷。但是房子i的涂色方式需要根據(jù)房子i-1的涂色方式來確定，所以我們對(duì)房子i-1要記錄涂三種顏色分別不同的開銷，這樣房子i在涂色的時(shí)候，我們就知道三種顏色各自的最小開銷是多少了。我們?cè)谠瓟?shù)組上修改，可以做到不用空間。

代碼 
public class Solution {
    public int minCost(int[][] costs) {
        if(costs != null && costs.length == 0) return 0;
        for(int i = 1; i < costs.length; i++){
            // 涂第一種顏色的話，上一個(gè)房子就不能涂第一種顏色，這樣我們要在上一個(gè)房子的第二和第三個(gè)顏色的最小開銷中找最小的那個(gè)加上
            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]);
        }
        // 返回涂三種顏色中開銷最小的那個(gè)
        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?
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

和I的思路一樣，不過這里我們有K個(gè)顏色，不能簡(jiǎn)單的用Math.min方法了。如果遍歷一遍顏色數(shù)組就找出除了自身外最小的顏色呢？我們只要把最小和次小的都記錄下來就行了，這樣如果和最小的是一個(gè)顏色，就加上次小的開銷，反之，則加上最小的開銷。

代碼 
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);
                // 找出最小和次小的，最小的要記錄下標(biāo)，方便下一輪判斷
                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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64696.html

相關(guān)文章

  • [LintCode/LeetCode] Paint House I & Paint Hous

    摘要：在原數(shù)組上動(dòng)規(guī)，每一行對(duì)應(yīng)一個(gè)房子，每一個(gè)元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個(gè)元素該元素的值上一行兩個(gè)與該元素不同列元素的值的較小者。不過這次要記錄三個(gè)變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...

    ChristmasBoy 評(píng)論0 收藏0

  • [Leetcode] Paint Fence 柵欄涂色

    摘要：假設(shè)是第一根柱子及之前涂色的可能性數(shù)量，是第二根柱子及之前涂色的可能性數(shù)量，則。遞推式有了，下面再討論下情況，所有柱子中第一根涂色的方式有中，第二根涂色的方式則是，因?yàn)榈诙涌梢院偷谝桓粯印? Paint Fence There is a fence with n posts, each post can be painted with one of the k colors. ...

    sixleaves 評(píng)論0 收藏0

  • leetcode 198 House Robber

    摘要：但是任何臨近的兩個(gè)房子被偷就會(huì)觸發(fā)警報(bào)。要求我們求出在不觸發(fā)警報(bào)的情況下偷到的最多的錢。每個(gè)房子里的錢通過輸入的數(shù)組表示。 題目詳情 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only...

    jzman 評(píng)論0 收藏0

  • LeetCode 337. House Robber III

    摘要：一番偵察之后，聰明的小偷意識(shí)到這個(gè)地方的所有房屋的排列類似于一棵二叉樹。如果兩個(gè)直接相連的房子在同一天晚上被打劫，房屋將自動(dòng)報(bào)警。計(jì)算在不觸動(dòng)警報(bào)的情況下，小偷一晚能夠盜取的最高金額。 Description The thief has found himself a new place for his thievery again. There is only one entranc...

    ymyang 評(píng)論0 收藏0

  • leetcode198,213 house robber

    摘要：你不能連著偷兩家因?yàn)檫@樣會(huì)觸發(fā)警報(bào)系統(tǒng)?，F(xiàn)在有一個(gè)數(shù)組存放著每一家中的可偷金額，問可以偷的最大金額為多少這里考驗(yàn)了動(dòng)態(tài)編程的思想。動(dòng)態(tài)編程要求我們將問題一般化，然后再找到初始情況開始這個(gè)由一般到特殊的計(jì)算過程。 House Robber I You are a professional robber planning to rob houses along a street. Each...

    whidy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<