来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

213 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

class Solution:def rob(self, nums: List[int]) -> int:#当偷窃的人家超过两家 则要考虑#考虑到情况1首位相连 当偷了第一家时，最后一家不能偷窃#情况2 当偷了最后一家时 第一家不能偷窃#dp[i] 表示第i次可以偷取的最高金额#dp[i] 递推公式dp[i]=max(dp[i-1],dp[i-2]+nums[i])if len(nums)<=2:return max(nums)else:nums_1=nums[0:-1]nums_2=nums[1:]dp_1=[0]*(len(nums_1))dp_1[0]=nums_1[0]dp_1[1]=max(nums_1[0],nums_1[1])dp_2=[0]*(len(nums_2))dp_2[0]=nums_2[0]dp_2[1]=max(nums_2[0],nums_2[1])for i in range(2,len(nums_1)):dp_1[i]=max(dp_1[i-1],dp_1[i-2]+nums_1[i])for j in range(2,len(nums_2)):dp_2[j]=max(dp_2[j-1],dp_2[j-2]+nums_2[j])return max(dp_1[-1],dp_2[-1])

337 打家劫舍III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
错误代码
我一开始想的是小偷只能偷某一层但是其实偷相邻层的同一边的孩子也不是直接相邻的，不会触发警报，思考错误

# 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[i] 为偷到第i层能窃取的最大金额#只能一层一层的偷#dp[i]=max(dp[i-1],dp[i-2]+sum(val))#遍历顺序 层次遍历dp=[0]*(100)dp[0]=root.valif not root.left and not root.right:return root.valque=[]sum_=0que.append(root.left)que.append(root.right)if root.left:sum_=sum_+root.left.valif root.right:sum_=sum_+root.right.valdp[1]=max(dp[0],sum_)for i in range(2,100):sum_=0flag=2**i#while(que)for j in range(0,flag):chi=que.pop(0)if chi:que.append(chi.left)que.append(chi.right)if chi.left:sum_=sum_+chi.left.valif chi.right:sum_=sum_+chi.right.valelse:que.append(TreeNode(0))que.append(TreeNode(0))# print(sum_)dp[i]=max(dp[i-1],dp[i-2]+sum_)if que:breakprint(dp)return dp[i]

正确代码

        #dp[i][0] 不偷节点i可以得到的最大值金额#dp[i][1]表示偷该节点可以得到的最大值金额#通过后序遍历树可以满足递归关系 如果抢了该节点，其孩子就不要动#如果没有偷该节点，可以考虑一下偷取孩子节点的金额#递归关系 父母dp[i][0]=max(dp[left][1],dp[left][1])+max(dp[right][1],dp[right][1])#   dp[i][1]=父母节点的val+dp[left][0]+dp[right][0]def tree(cur):if not cur:return 0,0left_tou,left_no=tree(cur.left)right_tou,right_no=tree(cur.right)val1=cur.val+left_no+right_noval2=max(left_tou,left_no)+max(right_tou,right_no)return val1,val2return max(tree(root))

121 买卖股票
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

class Solution:def maxProfit(self, prices: List[int]) -> int:#dp[i][0]表示第i天持有股票的最大现金 dp[i][0]表示第i天不持有股票的现金#递推关系 dp[i][0]=max(dp[i-1][0],-price[i])#dp[i][1]=max(dp[i-1][1],dp[i-1][0]+price[i])#初始化dp[0][0]=-price dp[0][1]=0dp=[[0]*2 for _ in range (len(prices))]dp[0][0]=-prices[0] dp[0][1]=0for i in range(1,len(prices)):dp[i][0]=max(dp[i-1][0],-prices[i])dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])return dp[-1][1]