leetcode(力扣) 198. 打家劫舍 (入门动态规划)

打家劫舍Ⅰ

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

思路分析

我是一个专业的小偷！！！！

据说这道题传播暴力，犯罪思想，即将被和谐？且做且珍惜哈哈，少有的有点意思的题了这是。

老规矩，五步走

1. 确定dp数组含义：
dp[i] 表示 偷i(含)之前的房屋，在不触发警报的情况下能偷到的最大金额。

2.状态转移公式：

将问题规模缩小，子问题化，对于当前某一房屋，可以选择偷或者不偷。
如果不偷，则自然dp[i] = d[i-1] 金额和前一个状态一样。
如果偷，则dp[i] = dp[i-2] + nums[i] ，偷当前房屋，则前一个房屋自然是不偷的，所以是dp[i-2]，然后再加上当前房屋的金额。

公式：dp[i] = max(dp[i-1],dp[i-2]+nums[i])

举例来说：1 号房间可盗窃最大值为 3 即为 dp[1]=3，2 号房间可盗窃最大值为 4 即为 dp[2]=4，3 号房间自身的值为 2 即为 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5。

思考的时候容易陷入全局的思维误区，当某个房间不偷的时候是dp[i] = dp[i-1],此时的i-1间房 不一定是偷还是不偷，其实这里没必要去花时间思考，因为从上面的例子可以看出来，只要子问题解决了，其他的情况就不需要过多考虑了。实际上比如 9,1,2,8,，是存在连续两间房不偷的，也存在[2,7,9,3,1] 这种一间偷一间不偷的。

3.初始化dp数组：

从公式可以看出来，某一项要依赖于前两项，所以初始化dp[0] = nums[0],dp[1] = max(nums[0],nums[1])。

4.确定遍历顺序：
这个就比较简单了，从前往后，没啥可说的

5.推导dp数组

这个就略了，一般程序出错之后才回来手推一下看看。

完整代码

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        if len(nums) == 1:
            return nums[0]
        # dp[i] 表示i（含）之前的房屋能偷盗的最多物品价值
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])

        print(dp)
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

打家劫舍 Ⅱ

在上一个题的基础上做了一点点提升，现在这些等待被偷的房子们组成了一个圈，也就是形成了一个环形，其余不变，那么也就是说为了不触发警报，第一家和最后一家只能偷其中一家，或者两家都不偷。

所以就有了下面三种情况

• 第一家和最后一家都不考虑
• 第一家考虑，最后一家不考虑
• 第一家不考虑，最后一家考虑

注意这里我用的是考虑，而不是必偷。

其实可以发现第二和第三种情况已经包括了第一种情况了。
换个思路，我们求的是能偷的最大金额，多一家可选肯定比少一家能偷的金额多，最次也是等于。所以第一种情况就可以不考虑了。

我们直接还是用上一题的代码，只不过调用它两次，分别传入第二种情况和第三种情况，取其中能偷到金额最大的那个就行啦。

有个细节要注意以下，就是如果传入的数组长度为1，或者经过切割之后长度为1，则直接返回就行了。不然会越界。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        def robrange(nums):
            if len(nums) == 1:
                return nums[0]
            dp = [0] * len(nums)

            # dp[i] 表示i（含）之前的房屋能偷盗的最多物品价值
            dp[0] = nums[0]
            dp[1] = max(nums[0],nums[1])
            for i in range(2,len(nums)):
                dp[i] = max(dp[i-1],dp[i-2]+nums[i])

            return dp[-1]
        # 考虑第一个不考虑最后一个 ,考虑最后一个不考虑第一个
        return max(robrange(nums[:-1]),robrange(nums[1:]))


    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22