网站建设费无形资产,兰州网站建设搜王道下拉,做动画人设有哪些网站可以借鉴,专做宝宝的用品网站198.打家劫舍
思路#xff1a;
1.确定dp数组#xff08;dp table#xff09;以及下标的含义#xff1a;dp[i]#xff1a;前 i 间房屋所能偷窃到的最高金额。
2.确定递推公式#xff1a;dp[i] max(dp[i - 2] nums[i-1], dp[i - 1])
i间房屋的最后一个房子是nums[i−…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 0dp [0 for _ in range(size 1)]dp[0] 0dp[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 0dp [0 for _ in range(size 1)]dp[0] 0dp[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.如果不选择根节点则可以选择左右儿子节点共四种可能
左子树选择根节点 右子树选择根节点左子树选择根节点 右子树不选根节点左子树不选根节点 右子树选择根节点左子树不选根节点 右子树不选根节点
选择其中最大值。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# 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)
