# **Leetcode筆記(House Robber)**
:::info
:information_source: 題目 : House Robber, 類型 : dynamic programming , 等級 : medium
日期 : 2023/02/25，2023/04/22，2023/06/13，2023/07/17，2023/09/28，2024/09/23
:::
### 嘗試
但沒有考慮到可能間隔2位取會更大，例如[2, 1, 1, 2]，取2, 2會更大
時間複雜度O(n)，空間複雜度O(n)
```python
class Solution:
def rob(self, nums: List[int]) -> int:
resl, resr = 0, 0
for i in range(0, len(nums), 2):
resl = resl + nums[i]
for j in range(1, len(nums), 2):
resr = resr + nums[j]
return max(resr, resl)
```
2023/06/13
用兩個變數，儲存pre和cur，pre為可以和現在這個數相加的，cur為它的前一個(所以不能加)，兩個一起比看誰比較大，後面更新繼續算
```python
class Solution:
def rob(self, nums: List[int]) -> int:
# 前前一個 / 前一個 / 暫時儲存
pre, cur, tmp = 0, 0, 0
for n in nums:
pre += n
tmp = cur
cur = max(pre, cur)
pre = tmp
return cur
```
2023/07/17
pre = 當前這個n + [0 : n - 1]
cur = [0 : n]
看這兩個哪一個比較大，更新給cur
```python
class Solution:
def rob(self, nums: List[int]) -> int:
pre, cur = 0, nums[0]
for n in nums[1 :]:
tmp = cur
cur = max(pre + n, cur)
pre = tmp
return cur
```
2023/09/28
```python
class Solution:
def rob(self, nums: List[int]) -> int:
cur, pre = 0, 0
maxRub = 0
for n in nums:
maxRub = max(maxRub, pre + n, cur)
pre = cur
cur = maxRub
return maxRub
```
2024/09/23
top down配合memoization，類似dfs但加上儲存功能，因為樹會高度重複
先從0開始，他會一路travese到最下面，新增一個base case是0，得到base case的答案之後，用公式去一步一步更新到最上面
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
memo = [0] * n
visited = set()
def traverse(i):
# base case for 4 and 5
if i >= n:
return 0
# already calculate the tree
if i in visited:
return memo[i]
res = max(nums[i] + traverse(i + 2), traverse(i + 1))
memo[i] = res
visited.add(i)
return res
traverse(0)
return memo[0]
```
bottom-up，記得要initialize對，dp[1]是取max(nums[0], nums[1])，dp永遠是儲存走到這步的最佳解
```python
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
# initialize
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])
return dp[n - 1]
```
---
### **優化**
真的不爽，前面的難題都看得懂，就這題這麼簡單都看不懂
4/22更
希望之後程式打不下去的時候，就放過自己跳下一題，或是去做其他事
時間複雜度是 $O(n)$，其中 $n$ 是房屋的數量
```python
class Solution:
def rob(self, nums: List[int]) -> int:
# 這兩個變量分別代表上一個和當前房屋抢劫後獲得的最大財富值
res_prev, res_now = 0, 0
for n in nums:
# 抢劫當前房屋後可以獲得的最大財富值
# 上一個房屋未被抢劫的最大財富值（res_prev）加上當前房屋的財富值 n
# 或者是上一個房屋被抢劫後的最大財富值（res_now）
tmp = max(res_prev + n, res_now)
# 完成了當前房屋的抢劫
res_prev = res_now
res_now = tmp
return res_now
```
---
**:warning: 錯誤語法**
:::warning
range(1,5,2) #代表从1到5，间隔2(不包含5)
不要搞相反
:::
**:thumbsup:學習**
:::success
:::
**思路**
**講解連結**
https://www.youtube.com/watch?v=73r3KWiEvyk
Provided by. NeetCode
https://www.youtube.com/watch?v=sqePf09p8Ag
Provided by. Peter刷Leetcode
###### tags: `dynamic programming` `medium` `leetcode`
Sign in with Wallet
Connect another wallet