Fork me on GitHub

打家劫舍

字数统计: 1.4k字   |   阅读时长≈ 5分

198. 打家劫舍

给定一个数组，相邻元素不能选，求元素之和的最大值。

示例 1:

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

示例 2:

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

思路

  • 动态规划基本题型，dp[i]表示到i为止可以偷到的最多钱
  • 先从最简单的情况入手，初始化dp数组：当数组长度为1时候，显然dp[0]=nums[0];当数组长度为2，最大值为两个数的max，所以dp[1]=max(num[0:2])
  • 求dp的递推公式：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24

    话不多说，show you the code
    ```python
    class Solution:
        def rob(self, nums: List[int]) -> int:
    # 方法一、基本DP
            n=len(nums)
            if not nums:return 0
            if n<=2:
                return max(nums)
            # dp[i]表示到i为止可以偷到的最多钱
            dp=[0]*len(nums)
            dp[0]=nums[0]
            dp[1]=max(nums[0:2])
            for i in range(2,n):
                #递推公式    
                dp[i]=max(dp[i-2]+nums[i],dp[i-1])
            return dp[-1]
    # 方法二、优化版DP
            pre,now=0,0
            for i in nums:
                # 迭代nums，pre变成now，now取now和pre+i的最大值
                pre ,now = now, max(pre+i,now)
            return now

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

1
2
3
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

1
2
3
4
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

思路

  • 与上题类似，唯一的区别就是数组的第一个和最后一个不能同时取
  • 因此可以将问题分解，把数组分为nums1=num[:-1],nums2=nums[1:],分别排除掉最后一个和第一个元素，分别求解出nums1和nums2能获得的最大值，最后二者取max

话不多说，show you the code:

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

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:return 0  
        if len(nums)<=2:return max(nums)
        # 和一条直线的版本一样，只要取把第一个和最后一个房子去掉的最大值就可以了

        # rob1函数即为上题的主函数
        def rob1(nums):
            if not nums:return 0
            n=len(nums)
            if n<=2:return max(nums)
            dp=[0]*n
            dp[0],dp[1]=nums[0],max(nums[0:2])
            for i in range(2,n):
                # 当前值为上一个取了，或者取了上上个和本个的最大值
                dp[i]=max(dp[i-2]+nums[i],dp[i-1])
            return dp[-1]

        # 和一条直线的版本一样，只要取把第一个和最后一个房子去掉的最大值就可以了
        return max(rob1(nums[:-1]),rob1(nums[1:]))

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

1
2
3
4
5
6
7
8
9
输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

1
2
3
4
5
6
7
8
9
10
输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

思路

  • 与上题类似，只是房子的排布变成了二叉树排列。
  • 定义一个树状dp，返回两个值，dp[0]表示抢了当前节点能获得的钱，dp[1]表示不抢的能获得的钱
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rob(self, root: TreeNode) -> int:
        if not root:return 0

        # dp[0]表示抢了当前节点能获得的钱，dp[1]表示不抢的
        def dp(root):
            # 确定dp的终止条件，空节点的话抢或者不抢都是0
            if not root:
                return 0,0

            # 递归左右子树
            l=dp(root.left)
            r=dp(root.right)

            # 如果抢了根节点，那么左右孩子都不能抢，所以rob=l[1]+r[1]+root.val
            rob=root.val+l[1]+r[1]

            # 如果根节点不抢，左右孩子不一定抢不抢，递归下去看，所以取max。
            skip=max(l)+max(r)

            return rob,skip
        return max(dp(root))
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北京邮电大学计算机硕士，研究方向：
Python、机器学习、深度学习
计算机视觉、NLP。

联系QQ:443563098

只做了一点微小的工作
谢谢大家