leetcode刷题-动态规划07

代码随想录动态规划part07|198.打家劫舍、213.打家劫舍II、337.打家劫舍III 198.打家劫舍213.打家劫舍II337.打家劫舍III -- 重做一遍

198.打家劫舍

leetcode题目链接 代码随想录文档讲解

思路：

这个房间偷与不偷与前几个房间有没有偷有关系 -> 动态规划

dp[i]数组的含义：到下标i间房（包含i）所偷的最大金币数为dp[i]，最终返回dp[numsize-1]dp[j] = max(dp[i-2]+nums[i], dp[i-1]) dp[i]考虑偷i(dp[i-2]+nums[i])和不偷i(dp[i-1])两种状态 不偷i，其实也包含了不偷i-1和偷i-1初始化，0, dp[0]=nums[0]; dp[1]=max(nums[0], nums[1])遍历顺序

python代码：

class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums) == 1: return nums[0] dp = [0]*(len(nums)+1) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] = max(dp[i-2]+nums[i], dp[i-1]) return dp[len(nums)-1] 213.打家劫舍II

leetcode题目链接 代码随想录文档讲解

思路：

上题是一个线性数组，本题将线性数组首尾连成环了，这样的话首元素和尾元素只能选一个或者都不选 划分为两种情况：1.考虑首元素不考虑尾元素； 2.考虑尾元素不考虑首元素 使用上题方法分别进行解决

python代码：

class Solution: def get_dp(self, nums): if not nums: return 0 if len(nums) == 1: return nums[0] dp = [0]*(len(nums)+1) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] = max(dp[i-2]+nums[i], dp[i-1]) return dp[len(nums)-1] def rob(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] dp1 = self.get_dp(nums[1:]) dp2 = self.get_dp(nums[:-1]) return max(dp1, dp2) 337.打家劫舍III – 重做一遍

leetcode题目链接 代码随想录文档讲解

思路： 二叉树结构，有相邻连接的线的不能偷；本题是树形bp入门级题目 三种方法：1️⃣暴力递归 2️⃣记忆化递归，在递归的时候把计算过的存储下来 3️⃣动态规划 每一层递归中都有一个长度为2的dp数组：dp[0]、dp[1]分别表示不偷与偷当前节点获得的最大金钱数 后序遍历：因为计算当前节点偷与不偷所得到的最大数量时要用到孩子的结果 遍历时分两种情况： 1. 偷这个节点value1，左右孩子都不偷 : value[i]+leftdp[0]+rightdp[0] 2. 不偷这个节点value2，左右孩子都可以偷的最大值: max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]) 3. return (value2, value1)

python代码：

# 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: # dp数组（dp table）以及下标的含义： # 1. 下标为 0 记录 **不偷该节点** 所得到的的最大金钱 # 2. 下标为 1 记录 **偷该节点** 所得到的的最大金钱 dp = self.traversal(root) return max(dp) # 要用后序遍历, 因为要通过递归函数的返回值来做下一步计算 def traversal(self, node): # 递归终止条件，就是遇到了空节点，那肯定是不偷的 if not node: return (0, 0) left = self.traversal(node.left) right = self.traversal(node.right) # 不偷当前节点, 偷子节点 val_0 = max(left[0], left[1]) + max(right[0], right[1]) # 偷当前节点, 不偷子节点 val_1 = node.val + left[0] + right[0] return (val_0, val_1)