House Robber I
- 1 min read
- LC-Medium
- Dynamic Programming
3 years ago
Solution (Memoization)
Pretty simple. Either rob the current house and move two houses ahead, or rob the next adjacent house.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(n) |
def rob(self, nums: List[int]) -> int:
memo = {}
def dfs(i):
if i >= len(nums):
return 0
if i not in memo:
memo[i] = max(nums[i] + dfs(i + 2), dfs(i + 1))
return memo[i]
return max(dfs(0), dfs(1))
Solution (Dynamic Programming)
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * n
dp.extend([0, 0])
for i in range(n - 1, -1, -1):
dp[i] = max(nums[i] + dp[i + 2], dp[i + 1])
return dp[0]