# 198. House Robber

{% embed url="<https://leetcode.com/problems/house-robber/>" %}

我以为 easy 题不会有 dp 的...

状态转换方程是 `maxRob(n) = max(maxRob(n-2) + nums[n-1], maxRob(n-1))` ，即完整nums不变情况下，n长度的最大rob值是 `(n-1)长度的最大rob` 和 `(n-2)长度最大rob + nums第n项` 中的较大值。

写出来的代码感觉不够dp style，改了个第二版，看起来更 dp 了但其实反而没第一版快。

{% tabs %}
{% tab title="V1" %}

```python
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        if len(nums) <= 2: return max(nums)
        
        dp = {0: 0, 1:nums[0], 2:max(nums[:2])}
        
        def maxRob(n):
            if n in dp: return dp[n]
            curMax = max(maxRob(n-2)+nums[n-1], maxRob(n-1))
            dp[n] = curMax
            return curMax
            
        return maxRob(len(nums))
```

{% endtab %}

{% tab title="V2" %}

```python
class Solution:
    def __init__(self):
        self.dp = dict()
        
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: self.dp[0] = 0
        elif n <= 2: self.dp[n] = max(nums)
        if n in self.dp: return self.dp[n]
        curMax = max(self.rob(nums[:n-2])+nums[n-1], self.rob(nums[:n-1]))
        self.dp[n] = curMax
        return curMax        
```

{% endtab %}
{% endtabs %}
