---
# System prepended metadata

title: '**Leetcode筆記(House Robber)**'
tags: [medium, dynamic programming, leetcode]

---

# **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
![image](https://hackmd.io/_uploads/BJilNFyCC.pn =80%x)
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永遠是儲存走到這步的最佳解
![image](https://hackmd.io/_uploads/B1lbTFyAR.png)

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