# leetcode 198 House rubber ###### tags: `leetcode` `algorithm` `easy` ## 問題說明 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. ``` Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. ``` ## 初步想法 由於題目只說不能連續搶兩家,不代表一定要隔一家搶,也就是說可能會有搶1、3、6家這樣的情況,所以不能單純的找出奇數index & 偶數index的和然後回傳比較的結果。 這邊需要用到dynamic programming的概念,將問題拆成小的subset,並利用這些subset得到最終的解答。我們變成要思考到每一家時,到目前為止可搶的最大金額為何,以範例來說 到第一家時可搶的最大金額就是 1(只有這個可以選) 到第二家時可搶的最大金額就是 2(取兩者中較大的一個) 到第三家時可搶的最大金額就是 4(由於不能連續搶,所以只能選1+3而非2+3) 到最後一家可搶的最大金額仍是 4(由於第四家+第二家的金額並沒有超過目前的最大總額,所以最大總額不會變動) 最後我們就會得到[1,2,4,4]這樣的最終搶劫金額陣列,回傳最後一個結果即為題目要求 ## 虛擬碼 若傳入的陣列長度為0 回傳0 若傳入的陣列長度為1 回傳nums[0] 建立搶劫總金額陣列totalRobbed = [] 優先處理陣列的前兩項,後續我們才能利用迴圈導出剩下的元素 totalRobbed[0] = nums[0] totalRobbed[1] = Math.max(nums[0],nums[1]) for (從2跑到nums.length - 1) { 第i項會是比較nums[i] + totalRobbed[i - 2] 與目前為止的最大額totalRobbed[i-1]的結果 } 回傳totalRobbed的最後一項 ## 最終程式碼 ``` var rob = function(nums) { if (!nums.length) return 0 if (nums.length === 1) return nums[0] const totalRobbed = [] totalRobbed[0] = nums[0] totalRobbed[1] = Math.max(nums[0], nums[1]) for (let i = 2; i < nums.length; i++) { totalRobbed[i] = Math.max(nums[i] + totalRobbed[i-2],totalRobbed[i - 1]) } return totalRobbed[totalRobbed.length - 1] }; ```