【代码随想录算法训练营】第48天 | 第九章 动态规划（九）+ 复习第20天 第六章 二叉树（四）

主要内容

打家劫舍

动态规划题目

198.打家劫舍

思路分析

dp[i]为考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
递推公式：① 偷dp[i], dp[i-2]+nums[i]
② 不偷dp[i],dp[i-1]

代码

class Solution:
    # dp[i]为考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
    # 递推公式：① 偷dp[i], dp[i-2]+nums[i]
    #          ② 不偷dp[i],dp[i-1]
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, n):
            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
14
15

213.打家劫舍II

思路分析

考虑两种情况：
1、不考虑首元素，考虑尾元素
2、不考虑尾元素，考虑首元素

代码

class Solution:
    # 两种情况，考虑首元素不考虑尾元素，考虑尾元素不考虑首元素
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return nums[0]
        res1 = self.robRange(nums, 0, n - 2)
        res2 = self.robRange(nums, 1, n - 1)
        return max(res1, res2)    



    def robRange(self, nums, start, end):
        if start == end:
            return nums[start]
        n = len(nums)
        dp = [0] * n
        dp[start] = nums[start]
        dp[start + 1] = max(nums[start], nums[start + 1])
        for i in range(start + 2, end + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[end]          
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

337.打家劫舍III

思路分析

后续遍历，递归

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # 后序遍历，返回当前结点偷与不偷得到的值
    def rob(self, root: Optional[TreeNode]) -> int:
        res = self.robTree(root)
        return max(res)

    def robTree(self, node):
        #[偷，不偷]
        if node is None:
            return [0, 0]
        resleft = self.robTree(node.left)
        resright = self.robTree(node.right)
        res1 = node.val + resleft[1] + resright[1]
        res2 = max(resleft) + max(resright)
        return [res1, res2]   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21