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 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.

翻譯

你是一個專業的小偷，今天你打算偷遍一整條街的房子，每間房子都一定有錢可以偷。不過有一個問題，就是房子之間有設警報系統，如果你連偷兩間相鄰的房子，警報系統就會引來警察，你就會被抓。

這邊會給一個list，裡面每個元素都代表這間房子內可以偷到的錢，你要怎麼安排你的偷竊計畫才能偷到最多的錢而且不會驚動警察。

範例：
[2,4,5,3]，最多可以偷到 2+5+3 = 10，因為4+5+3 = 12雖然可以拿到比較多錢，但是會被警察抓。

思路

1. 這題跟LeetCode 121. Best Time to Buy and Sell Stock很像，我們需要計算每間房子可以偷得多少錢，因此需要一個maxS陣列才儲存偷到目前房子最多可以拿到多少錢。
2. [m0,m1,m2,m3,....]，如果房子只有一間[m0]，可以偷到的錢為max = mo
3. 如果有房子兩棟[m0,m1]，那最多可以拿到m0,m1之中較大的錢 max = Max(m0,m1)
4. 三棟房子的情況[m0,m1,m2]，最多拿到 max = Max(m0+m2,m1);
5. 因此可以得到，目前房子n，可以拿到的錢
   max = Max( 現在這棟 + 前前一可以拿到的最大金額 , 前一棟可以拿到的最大金額 )

解題

/**
 * @param {number[]} nums
 * @return {number}
 * 
 * 
 * 
 */
var rob = function(nums) {
    var maxS = new Array();
    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0];
    if(nums.length === 2) return Math.max(nums[1],nums[0]);

    maxS.push(nums[0]);
    maxS.push(Math.max(nums[0],nums[1]));

    for(var i = 2 ; i < nums.length ; i++){
        //最大金額   = Max(現在金額+前前一棟最大金額 ， 前一棟最大金額)
        maxS[i] =  Math.max(nums[i] + maxS[i-2] , maxS[i-1]);;
    }
    return maxS.pop();
};