House Robber
franklinqin0 RecursionDFSDP
# Solution
# Recursion w/ Memoization
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
csum = [0 for _ in range(n)]
csum[0] = nums[0]
csum[1] = max(csum[0], nums[1])
for i in range(2, n):
csum[i] = max(csum[i-1], csum[i-2] + nums[i])
return csum[-1]
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# Iterative DP
def rob(self, nums: List[int]) -> int:
n = len(nums)
memo = {}
memo[0] = nums[0]
if n >= 2: memo[1] = max(nums[0], nums[1])
def dfs(i):
if i in memo:
return memo[i]
memo[i] = max(dfs(i-1), dfs(i-2) + nums[i])
return memo[i]
return dfs(n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13