House Robber

RecursionDFSDP
https://leetcode.com/problems/house-robber

# Solution

# Recursion w/ Memoization

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    @cache
    def dfs(i):
        if i < 0:
            return 0
        res = max(dfs(i-1), dfs(i-2)+nums[i])
        return res
    return dfs(n-1)
1
2
3
4
5
6
7
8
9
def rob(self, nums: List[int]) -> int:
    n = len(nums)
    memo = [-1 for _ in range(n)]

    def dfs(i):
        if i < 0:
            return 0
        if memo[i] != -1:
            return memo[i]
        res = max(dfs(i-1), dfs(i-2)+nums[i])
        memo[i] = res
        return res
    return dfs(n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13

# Iterative DP

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    dp = [0 for _ in range(n+2)]
    for i in range(2, n+2):
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-2])
    return dp[-1]
1
2
3
4
5
6

House Robber III