代码随想录算法训练营Day 47|动态规划part09|198.打家劫舍、213.打家劫舍II 、337.打家劫舍III

代码随想录算法训练营Day 47|动态规划part09|198.打家劫舍、213.打家劫舍II 、337.打家劫舍III

---

---

198.打家劫舍

题目链接

一、法一

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # dp[i]表示：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
        dp=[0]*len(nums)
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return nums[0]
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            # 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额
            # 偷第i个：dp[i-2]+nums[i] 不偷第i个：dp[i-1]
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[len(nums)-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

213.打家劫舍II

题目链接

一、法一

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        # 包含首元素不包含尾元素
        result1=self.rob_1(nums[0:len(nums)-1])
        # 包含尾元素不包含首元素
        result2=self.rob_1(nums[1:len(nums)])
        return max(result1,result2)
    def rob_1(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # dp[i]表示：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
        dp=[0]*len(nums)
        if len(nums)==0:
            return 0
        if len(nums)==1:
            return nums[0]
        dp[0]=nums[0]
        dp[1]=max(nums[0],nums[1])
        for i in range(2,len(nums)):
            # 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额
            # 偷第i个：dp[i-2]+nums[i] 不偷第i个：dp[i-1]
            dp[i]=max(dp[i-1],dp[i-2]+nums[i])
        return dp[len(nums)-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
30
31
32
33

---

337.打家劫舍III

题目链接

一、法一

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rob(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        dp=self.tranveral(root)
        return max(dp[0],dp[1])
        # dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
    def tranveral(self,node):
        if not node:
            return [0,0]
        leftdp=self.tranveral(node.left)
        rightdp=self.tranveral(node.right)
        # 偷node,左右子节点都不偷
        val1=node.val+leftdp[0]+rightdp[0]
        # 不偷node，左右子节点都偷
        val0=max(leftdp[1],leftdp[0])+max(rightdp[0],rightdp[1])
        return [val0,val1]
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