198.House Robber === ###### tags: `Medium`,`Array`,`DP` [198. House Robber](https://leetcode.com/problems/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 systems connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**. Given an integer array `nums` representing the amount of money of each house, return *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. ``` **Example 2:** ``` Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12. ``` **Constraints**: * 1 <= `nums.length` <= 100 * 0 <= `nums[i]` <= 400 ### 解答 #### Javascript 解法一 Time: $O(n)$ Space: $O(n)$ ```javascript= function rob(nums) { if (nums.length === 0) return 0; if (nums.length === 1) return nums[0]; if (nums.length === 2) return Math.max(nums[0], nums[1]); const dp = []; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (let i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[nums.length - 1]; } ``` 解法二 Time: $O(n)$ Space: $O(1)$ ```javascript= function rob(nums) { let max = 0; let prevMax = 0; for (let i = 0; i < nums.length; i++) { const temp = max; max = Math.max(prevMax + nums[i], max); prevMax = temp; } return max; } ``` > 解法一是好久以前寫的,真的是圖樣圖森破 > [name=Marsgoat][time= Dec 14, 2022] #### C# ```csharp= public class Solution { public int Rob(int[] nums) { if (nums.Length == 1) return nums[0]; int amount1 = nums[0]; int amount2 = Math.Max(nums[0], nums[1]); for(int i = 2; i < nums.Length; i++){ int amount = Math.Max(amount2, amount1 + nums[i]); amount1 = amount2; amount2 = amount; } return amount2; } } ``` > [name=Jim][time= Dec 14, 2022] #### Python ```python= class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums[0], nums[1]) dp = [nums[0], max(nums[0], nums[1])] for i in range(2, len(nums)): dp.append(max(dp[i-2] + nums[i], dp[i-1])) return dp[-1] ``` > General Solution ```python= class Solution: def rob(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] if len(nums) == 2: return max(nums[0], nums[1]) first, second = nums[0], max(nums[0], nums[1]) for i in range(2, len(nums)): curr = max(first + nums[i], second) first = second second = curr return second ``` > Constant Space Solution > [name=Kobe][time= Dec 14, 2022] ```python= class Solution: def rob(self, nums: List[int]) -> int: cur, pre = 0, 0 for n in nums: cur, pre = max(cur, pre + n), cur return cur ``` > [name=Yen-Chi Chen][time=Wed, Dec 14, 2022] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)