学习资料：https://programmercarl.com/0198.打家劫舍.html#算法公开课
动态规划的打家劫舍系列和股票买卖系列（股票还有贪心算法可解）
学习记录：
198.打家劫舍（一维dp数组，前n间房子都可偷的情况下的最高金额，每间房子偷数都是由前一间和前两间决定）
点击查看代码
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 先考虑特殊情况
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
# 动态规划之打家劫舍
# dp[i]代表当考虑从第一间房子到第i间房子都可以偷的时候的最高金额，不一定偷第i间
dp = [0]*len(nums)
# 初始化，若只考虑i=0则必须偷第一间
dp[0]=nums[0]
# 如果i=1，则选择性地偷第一或第二间，反正金额要最大
dp[1] = max(nums[0], nums[1])
# 从第三间房间开始遍历
for i in range(2, len(nums)):
# 递推，动态转移方程，要么偷第i间和第i-2间，要么偷第i-1间
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
return dp[-1]
213.打家劫舍2（把环形分割为3类情况）
点击查看代码
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 先考虑特殊情况，没有房子或者只有一栋房子
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
# 环形排布的破题点：分为三种情况，1有头无尾，2无头无尾，3无头有尾；但是这道题1和3都包括了2所以只考虑1、3
# 再对这两种情况分别调用非环形房子时的打家劫舍问题解法
result1 = self.robRange(nums, 0, len(nums)-2)
result2 = self.robRange(nums, 1, len(nums)-1)
return max(result1, result2)
def robRange(self, nums, start, end):
"""还是跟打家劫舍1有点区别，那种头指针为0，尾指针为len(nums)-1，这里对应的start和end"""
if start == end:
return nums[start]
pre_max = nums[start]
cur_max = max(nums[start], nums[start+1])
for i in range(start+2, end+1):
temp = cur_max
cur_max = max(cur_max, pre_max+nums[i])
pre_max = temp
return cur_max
337.打家劫舍3（树形DP问题，递归，左右根遍历，由左右子树来判断父节点）
点击查看代码
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def rob(self, root):
"""
:type root: Optional[TreeNode]
:rtype: int
"""
# 调用递归函数，返回的是偷或者不偷时的最高金额，是一个元组
dp = self.traversal(root)
# 返回两种情况的最大值
return max(dp)
def traversal(self, node):
"""树形dp，二叉树，递归，后序遍历"""
# 父节点dp=[val0, val1], val0代表不偷该节点的最高金额，val1代表偷该节点（那就不能偷左右子节点）的最大金额
if not node:
return (0,0)
# 左
left = self.traversal(node.left)
# 右
right = self.traversal(node.right)
# 根
# 情况1：不偷此父节点，则左右子节点可偷可不偷
val_0 = max(left[0], left[1])+ max(right[0], right[1]) # 分别考虑偷不偷该子节点获得的金额更大
# 情况2：偷该父节点，则左右子节点都不偷
val_1 = node.val + left[0] + right[0]
return (val_0, val_1)
121.买卖股票的最佳时机（二维dp数据，是否持股的两个状态对应的金额）
点击查看代码
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 动态规划：股票问题
# dp[i][0]代表第i天是持有股票的状态下的金额，dp[i][1]代表第i天是不持有股票的状态下的金额，但是并不清楚是具体哪天买入卖出
length = len(prices)
if length == 0:
return 0
dp = [[0]*2 for _ in range(length)] # 要用二维数组
# 初始化
# 第一天的状态要么没买入
dp[0][1] = 0
# 要么第一天买入
dp[0][0] = -prices[0]
# 开始从前到后遍历
for i in range(1, length):
# 递归函数，根据前一天的状态决定
# 若今天有股票，可能是前一天就有的，也可能前一天没有而今天刚买入
dp[i][0] = max(dp[i-1][0], -prices[i]) # -prices[i]是因为只能买卖一次，前面总金额为0，此时花掉这么多
# 若今天没有股票，可能是前一天就没有，或者前一天有而今天刚卖出
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
return dp[-1][1] # 最后的最大价值必然是最后一天已经卖出去的状态才有的
122.买卖股票的最佳时机2（可多次买卖这支股票，与121的区别在于,当第i天持股且前一天不持股的情况下，前一天总金额可能非0）
点击查看代码
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# dp[i][0]代表第i天是处于持有股票的状态对应的利润，dp[i][1]代表第i天没有股票对应的利润
length = len(prices)
# if length == 0:
# return 0
# 构造dp二维数组
dp = [[0]*2 for _ in range(length)]
# 初始化
dp[0][0] = -prices[0] # 第一天买入股票
dp[0][1] = 0 # 第一天没有股票
# 开始遍历
for i in range(1, length):
# 第i天没有股票，可能前一天也没有(但是可能前面买卖过，总金额非0), 也可能前1天就有而今天卖了
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
# 第i天有股票，可能前一天就有，可能前一天没有今天刚买入（前面可能总金额非0）
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
return dp[-1][1]
123.买卖股票的最佳时机3（与前两种相比，这里分了5种状态分别考虑，难）
点击查看代码
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 分为5种状态
# dp[i][0]：没有操作
# dp[i][1]:第i天第一次持有股票
# dp[i][2]:第i天第一次不持有股票，也不一定是第i天卖出的，可能是前几天
# dp[i][3]:第i天第二次持有股票
# dp[i][4]:第i天第二次不持有股票
length = len(prices)
if length==0:
return 0
# 构造5维dp数组
dp = [[0]*5 for _ in range(length)]
# 初始化和
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
# 开始遍历
for i in range(1, length):
# 根据5种情况写出5种递归函数，由前一天得到
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) # 前一天也第一次持股，或者前一天没有而今天第一次持股
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
return dp[-1][4]
PS:比背包好理解，但是还是想不到，多复习
今天天气阴沉沉黑乎乎，啥时候下雨啊
终于赶上进度了，勉勉强强，好饿