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)