198.打家劫舍
思路：
1.确定dp数组（dp table）以及下标的含义：dp[i]：前 i 间房屋所能偷窃到的最高金额。
2.确定递推公式：dp[i] = max(dp[i - 2] + nums[i-1], dp[i - 1])
i间房屋的最后一个房子是nums[i−1]。
如果房屋数大于等于 2 间，则偷窃第 i−1 间房屋的时候，就有两种状态：
-
偷窃第 i−1 间房屋，那么第 i-2 间房屋就不能偷窃了，偷窃的最高金额为：前 i−2 间房屋的最高总金额 + 第 i−1 间房屋的金额，即 dp[i]=dp[i−2]+nums[i-1]；
-
不偷窃第 i−1 间房屋，那么第 i−2 间房屋可以偷窃，偷窃的最高金额为：前 i−1 间房屋的最高总金额，即 dp[i]=dp[i−1]。
-
初始条件：
-
前 0 间房屋所能偷窃到的最高金额为 0，即 dp[0]=0。
-
前 1 间房屋所能偷窃到的最高金额为 nums[0]，即：dp[1]=nums[0]。
-
-
确定遍历顺序：dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历
class Solution:
def rob(self, nums: List[int]) -> int:
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size + 1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, size + 1):
dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
return dp[size]
213.打家劫舍II
思路：
这道题可以看做是「198. 打家劫舍」的升级版。
如果房屋数大于等于 3 间，偷窃了第 1 间房屋，则不能偷窃最后一间房屋。同样偷窃了最后一间房屋则不能偷窃第 1 间房屋。
假设总共房屋数量为size，这种情况可以转换为分别求解 [0,size−2] 和 [1,size−1] 范围下首尾不相连的房屋所能偷窃的最高金额，然后再取这两种情况下的最大值。而求解 [0,size−2] 和 [1,size−1] 范围下首尾不相连的房屋所能偷窃的最高金额问题就跟「198. 打家劫舍」所求问题一致了。
class Solution:
def helper(self, nums):
size = len(nums)
if size == 0:
return 0
dp = [0 for _ in range(size + 1)]
dp[0] = 0
dp[1] = nums[0]
for i in range(2, size + 1):
dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1])
return dp[size]
def rob(self, nums: List[int]) -> int:
size = len(nums)
if size == 1:
return nums[0]
ans1 = self.helper(nums[:size - 1])
ans2 = self.helper(nums[1:])
return max(ans1, ans2)
337.打家劫舍III
思路：
树形动态规划问题。
对于当前节点 cur，不能选择子节点，也不能选择父节点。所以对于一棵子树来说，有两种情况：
- 选择了根节点
- 没有选择根节点
1.选择根节点
如果选择了根节点，则不能再选择左右儿子节点，这种情况下的最大值为：当前节点 + 左子树不选择根节点 + 右子树不选择根节点。
不选择根节点
2.如果不选择根节点，则可以选择左右儿子节点，共四种可能：文章来源：https://www.toymoban.com/news/detail-451978.html
- 左子树选择根节点 + 右子树选择根节点
- 左子树选择根节点 + 右子树不选根节点
- 左子树不选根节点 + 右子树选择根节点
- 左子树不选根节点 + 右子树不选根节点
选择其中最大值。文章来源地址https://www.toymoban.com/news/detail-451978.html
# 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)
到了这里，关于算法记录 | 48 动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
