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

資訊專欄INFORMATION COLUMN

leetcode 198 House Robber

jzman / 796人閱讀

摘要：但是任何臨近的兩個(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 constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
題目的意思是，我們是一個(gè)江洋大盜～現(xiàn)在我們要去偷整條街的房子，每個(gè)房子里有一定的錢。但是任何臨近的兩個(gè)房子被偷就會(huì)觸發(fā)警報(bào)。要求我們求出在不觸發(fā)警報(bào)的情況下偷到的最多的錢。每個(gè)房子里的錢通過輸入的int數(shù)組表示。
想法

動(dòng)態(tài)規(guī)劃問題

對于每一個(gè)房子，我們有偷／不偷兩種選擇

因此我們聲明兩個(gè)變量prevNo和prevYes分別保存，我沒偷/偷了當(dāng)前房子的情況下，目前為止偷的最多的錢數(shù)。

如果想偷當(dāng)前房子，那么要求我們并沒有偷前一個(gè)房子，所以用前一個(gè)房子的prevNo值和當(dāng)前房子的錢數(shù)相加。

如果不偷當(dāng)前房子，那我們可以取前一個(gè)房子的prevNo值和prevYes值中較大的那個(gè)。

解法 
    public int rob(int[] nums) {
                int prevNo = 0;
        int prevYes = 0;
        
        for(int n: nums){
            int temp = prevNo;
            prevNo = Math.max(prevNo, prevYes);
            prevYes = temp+n;
        }
        
        return Math.max(prevNo, prevYes);
    }

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

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

相關(guān)文章

  • 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 評論0 收藏0

  • [LeetCode] House Robber I II

    摘要：注意對邊界條件的判斷，是否非空，是否長度為 House Robber I Problem You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping y...

    qpal 評論0 收藏0

  • [Leetcode] House Robber 打家劫舍

    摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路一般來說，給定一個(gè)規(guī)則，讓我們求任意狀態(tài)下的解，都是用動(dòng)態(tài)規(guī)劃。另外我們可以做一點(diǎn)優(yōu)化，本來我們是要用一個(gè)數(shù)組來保存之前的結(jié)果的。所以我們分別算出這兩個(gè)條件下的最大收益，然后取更大的就行了。可以復(fù)用的代碼。 House Robber I You are a professional robber planning to rob houses along a ...

    golden_hamster 評論0 收藏0

  • LeetCode[337] House Robber III

    摘要：復(fù)雜度思路對于每一個(gè)位置來說，考慮兩種情況分別對和再進(jìn)行計(jì)算。用對已經(jīng)計(jì)算過的進(jìn)行保留，避免重復(fù)計(jì)算。 LeetCode[337] House Robber III The thief has found himself a new place for his thievery again. There is only one entrance to this area, calle...

    Dr_Noooo 評論0 收藏0

  • [LintCode/LeetCode] House Robber II

    摘要：因?yàn)槿×岁?duì)首就不能取隊(duì)尾，所以對數(shù)組循環(huán)兩次，一個(gè)從取到，一個(gè)從取到，比較兩次循環(huán)后隊(duì)尾元素，取較大者。注意，要先討論當(dāng)原數(shù)組位數(shù)小于時(shí)的情況。 Problem After robbing those houses on that street, the thief has found himself a new place for his thievery so that he wi...

    OnlyLing 評論0 收藏0

發(fā)表評論

0條評論

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