题目大意，一个强盗沿着一排房子盗窃，强盗不能盗连续的两个房子，求强盗能盗窃的最大值. 比如6个房子，强盗抢劫每个房子得到的值为 nums = [3, 1, 5, 3, 7, 9]。最大获利为 3 + 5 + 9 = 17.
解题思路：
这个题如果用brute force直接解的话会超时，brute force每个房子有两个可能，robber or not，所以n个房子的时间复杂度是\(O(2^n)\)。直接超时。
可以用动态规划来解：
假设 d[i] = max money for up to ith home
那么 d[i] = max(d[i - 1], d[i - 2] + nums[i])
这种题目通常可以用记忆化递归，或者递推来解。通常可以进行空间压缩。
1. recursion with memorization
class Solution(object):
def rob(self, nums):
n = len(nums)
res = [-1 for _ in range(n)]
def dp(nums, i, res):
if i < 0:
return 0
if res[i] >= 0:
return res[i]
else:
res[i] = max(dp(nums, i - 1, res), dp(nums, i - 2, res) + nums[i])
return res[i]
return dp(nums, n - 1, res)
2. 递推/动态规划
class Solution(object):
def rob(self, nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
d = [0 for _ in range(n)]
d[0] = nums[0]
d[1] = max(nums[0], nums[1])
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2] + nums[i])
return d[n - 1]
3. 递推/动态规划 + 压缩空间
class Solution(object):
def rob(self, nums):
n = len(nums)
if n == 0:
return 0
dp1 = 0
dp2 = 0
for i in range(n):
curr = max(dp1, dp2 + nums[i])
dp2 = dp1
dp1 = curr
return curr