Leetcode初级算法打家劫舍（动态规划）（Python实现）

左手的ㄟ右手 2022-05-05 23:54 231阅读 0赞

问题描述：

![70][]

算法思想：

该问题的内在逻辑结构依然是动态规划里的经典结构。最关键的是推出状态转移方程，当前规模的对应解法由更低规模的解法，仿佛拾级而上，站在前人的肩膀上不断攀登。

实际操作起来，比较实用的方法如下：固定一个比较小的规模n， 进行思维实验。

例子：

nums = [2,7,9,3,1]，求这个数组对应的最高金额。

我们要做的是拿着某个规模的解，去求更高规模的解。用数组memo记录每个规模对应的解（最高金额），memo\[i\]对应的是nums的子数组nums\[:i\]（子问题）对应的解（最高金额）。这个过程就是从左向右顺序扫描nums数组，一边扫描一边将求出的解存储为memo\[i\]。假定现在扫描到i = 3，此时子数组为nums\[:3\] = \[2,7,9\]，我们来手算一下memo，得到memo\[:3\] = \[2, 7, 11\]。

好了，现在扫描到nums下一项，i = 4，nums\[:4\] = \[2,7,9,3\]，现在我们来求memo的第四项，也就是下一规模的解。对应这第四个屋子（nums\[3\] = 3），作为一个贼我们有两个选择：偷或是不偷。如果我没有偷第三家屋子，那就不用担心偷第四家会触发报警，那就放心偷好了；如果我偷了第三家，那就要斟酌一下偷不偷第四家了。偷第四家就必定要放弃第三家，但如果第四家钱特别多，那还是不亏的。i = 3时我们的选择是偷2 和 9，收益是11；i = 4时，如果偷3就只能 7+3，收益是10，不划算，果断不偷。memo更新为\[2,7,11,11\]。

类似地，继续扫描，i = 5，nums\[:5\] = \[2,7,9,3,1\],还是那个问题——这家屋子偷还是不偷。因为我们放弃了第四家，不存在相邻问题，放心偷就好。

发现规律了吗？下一规模的解，也就是memo\[n\]，要么是memo\[n-1\] （不偷，保持原状），或是memo\[n-2\]+nums\[n\]（放弃上一家，偷这家）。由于程序不知道上一家有没有偷，我们两个选择都算一下，取较大值即可。

代码：

class Solution(object):  
    def rob(self, nums):  
        """  
        :type nums: List\[int\]  
        :rtype: int  
        """  
        if nums == \[\]:  return 0  
        n = len(nums)  
        if n == 1:  return nums\[0\]  
        memo = \[nums\[0\] for i in range(n)\]  
        memo\[1\] = max(nums\[:2\])  
        for i in range(2,n):  
            choice1 = memo\[i-1\]  
            choice2 = memo\[i-2\]+nums\[i\]  
            memo\[i\] = max(choice1,choice2)  
        return memo\[n-1\]

[70]: /images/20220506/0faf337220b74fc1a285ddd9ffee5d66.png