198.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

# Author: Yu Zhou
# 198. House Robber

# DP的思路是比对dp[i-2]+nums[i] 和dp[i-1]的值
# 状态：从0到i，不能选择相邻节点得到的最大值

# DP
# 时间/空间 O(N)

classSolution(object):
defrob(self, nums):
"""
 :type nums: List[int]
 :rtype: int
 数学公式
 f(0) = nums[0]
 f(1) = max(f(0), f(1))
 f(2) = max(nums(2)+ f(0), f(1))
 f(3) = max(nums(3)+ f(1), f(2))
 .
 .
 f(n) = max(nums(n) + f(n-2), f(n-1))
 """
# Edge
ifnotnums:
return0
iflen(nums) ==1:
returnnums[0]


# Creating dp
dp= [0foriinxrange(len(nums))]
dp[0] =nums[0]
dp[1] =max(nums[0], nums[1])

# DP
foriinxrange(2, len(nums)):
dp[i] =max(nums[i] +dp[i-2], dp[i-1])

returndp[-1]