198 house robber
198. House Robber
题目: https://leetcode.com/problems/house-robber/
难度:
Easy
状态转移方程:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
AC 代码
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0 : return 0
elif n == 1 : return nums[0]
elif n == 2 : return max(nums[0], nums[1])
else:
dp = [0 for i in range(n)]
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,n):
dp[i] = max( dp[i-1], dp[i-2] + nums[i])
return dp[n-1]
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last, now = 0, 0
for i in nums: last, now = now, max(last + i, now)
return now
