256. Paint House

Miracle 發(fā)布于2019-08-14 14:08 / 648人閱讀

摘要：題目解答這類題還是先找臨時的結果，由臨時的結果最終推出最終解。比如說用存到個的時候最小的但是到第個的時候，有三種情況涂當我涂紅的時候，前面一個只能涂藍或者綠，所以我只能加上這兩種情況的最小值，作為此次計算的最小值，以此類推。

題目：
here 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.

解答：
這類題還是先找臨時的結果，由臨時的結果最終推出最終解。比如說用f(i, j)存到i個house的時候最小的cost.但是到第i個house的時候，有三種情況：涂red, blue or green.當我涂紅的時候，前面一個只能涂藍或者綠，所以我只能加上這兩種情況的最小值，作為此次計算的最小值，以此類推。

public class Solution {
    //State: f[i][j] is the minimum cost of painting i houses with color j -> (red, blue, green)
    //Function: f[i][0] = Math.min(f[i - 1][1], f[i - 1][2]) + costs[i][0]
    //          f[i][1] = Math.min(f[i - 1][0], f[i - 1][2]) + costs[i][1]
    //          f[i][2] = Math.min(f[i - 1][0], f[i - 1][1]) + costs[i][2]
    //Initialize: f[0][0] = costs[0][0], f[0][1] = costs[0][1], f[0][2] = costs[0][2];
    //Result: Math.min(f[costs.length - 1][0], f[costs.length - 1][1], f[costs.length - 1][2]);
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        
        int house = costs.length, color = costs[0].length;
        int[][] f = new int[house][color];
        //Initialize
        f[0][0] = costs[0][0];
        f[0][1] = costs[0][1];
        f[0][2] = costs[0][2];
        //Function
        for (int i = 1; i < house; i++) {
            f[i][0] = Math.min(f[i - 1][1], f[i - 1][2]) + costs[i][0];
            f[i][1] = Math.min(f[i - 1][0], f[i - 1][2]) + costs[i][1];
            f[i][2] = Math.min(f[i - 1][0], f[i - 1][1]) + costs[i][2];
        }
        
        return Math.min(f[house - 1][0], Math.min(f[house - 1][1], f[house - 1][2]));
    }
}

GPU云服務器云服務器 House Paint wm paint t256

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64830.html

[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原數(shù)組上動規(guī)，每一行對應一個房子，每一個元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個元素該元素的值上一行兩個與該元素不同列元素的值的較小者。不過這次要記錄三個變量本行最小值，本行第二小值，本行最小值下標。 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 House 房子涂色

摘要：動態(tài)規(guī)劃復雜度時間空間思路直到房子，其最小的涂色開銷是直到房子的最小涂色開銷，加上房子本身的涂色開銷。我們在原數(shù)組上修改，可以做到不用空間。代碼找出最小和次小的，最小的要記錄下標，方便下一輪判斷 Paint House There are a row of n houses, each house can be painted with one of the three colors...

SunZhaopeng 2019-08-14 12:46 評論0 收藏0
265. 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 w...

mylxsw 2019-08-14 14:08 評論0 收藏0
276. Paint Fence

摘要：代碼如下表示跟前面不一樣顏色，表示跟前面一樣顏色跟前面不一樣顏色的話，在這輪有種可能性跟前面一樣顏色的話，在這輪有種可能性，且前一輪不能與前前一輪一樣顏色因為這個的解法里，我們只用到變量和，所以我們可以進定步把空間復雜度降為題目：There is a fence with n posts, each post can be painted with one of the k colo...

zhjx922 2019-08-14 14:08 評論0 收藏0
Redis新手指南：在node中使用redis

摘要：簡介是一個高性能的數(shù)據(jù)庫，把數(shù)據(jù)存在內(nèi)存中，并在磁盤中記錄數(shù)據(jù)的變化。因為將數(shù)據(jù)存在內(nèi)存中，所以數(shù)據(jù)操作非?？?。在中使用首先，安裝驅動支持多種數(shù)據(jù)類型，常用的有鍵值對，哈希表，鏈表，集合等。鍵值對運行，結果如下哈希表哈希表有點類似中的。 Redis簡介 Redis是一個高性能的key-value數(shù)據(jù)庫，Redis把數(shù)據(jù)存在內(nèi)存中，并在磁盤中記錄數(shù)據(jù)的變化。因為將數(shù)據(jù)存在內(nèi)存中，所以數(shù)據(jù)...

pcChao 2019-08-23 10:40 評論0 收藏0