一、题目
House Robber
二、解题
题目说了一个小偷和警察的故事，其实意思就是输入一个整数序列，然后求出任意不相邻的数加起来的最大的和。
首先想到的就是递归，只有两种情况，从第一个数开始计算，或者从第二个数开始计算，返回两个值中较大的一个。
注意跳出条件，可能最后的列表只剩下1,2,3的情况。
三、尝试与结果
class Solution(object):
def rob(self, nums):
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return nums[0] if nums[0] >nums[1] else nums[1]
if len(nums) == 3:
if nums[1] > nums[0] + nums[2]:
maxValue = nums[1]
else:
maxValue = nums[0] + nums[2]
return maxValue
firstBegin = nums[0] + self.rob(nums[2:])
secondBegin = nums[1] + self.rob(nums[3:])
maxValue = firstBegin if firstBegin > secondBegin else secondBegin
return maxValue
结果：TL
对于输入序列:
listh = [155,44,52,58,250,225,109,118,211,73,137,96,137,89,174,66,134,26,25,205,239,85,146,73,55,6,122,196,128,50,61,230,94,208,46,243,105,81,157,89,205,78,249,203,238,239,217,212,241,242,157,79,133,66,36,165] 花费了3.8s
超时
再次尝试：
看到Tags提示了动态规划。。
class Solution(object):
def rob(self, nums):
d = dict()
resultValue = 0
for i in range(0,len(nums)):
d[i] = nums[i]
for j in range(0,i):
if j + 1 < i and d[j] + nums[i] > d[i]:
d[i] = d[j] + nums[i]
if d[i] > resultValue:
resultValue = d[i]
return resultValue
结果：AC
四、理解与记录
我对动态规划的理解
- 跟递归相反，递归是从最大往最小推，DP是从小往大推（一般都是从d[0]开始的）
- 想得出d[i]的值，是通过已经算出的前面的所有d[j]的值来得出的（区域求值）
- DP一般都是使用循环O(n2)，当然根据状态和状态转移方程不同，可以有更好的解法
