一、题目

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)，当然根据状态和状态转移方程不同，可以有更好的解法