题目描述
blablabla
样例
blablabla
时间复杂度 O(n)
Python3 代码
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
n = len(nums)
if n ==1:
return nums[0]
dp = [nums[0]]*n
dp[1] = max(nums[1],nums[0])
if n==2:
return dp[1]
for i in range(2, n):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[n-1]