21.多重背包
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
class Solution:
def test_multi_pack(self,bag_weight, weight, nums, value):
dp = [0] * (bag_weight + 1)
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# 以上是01背包，加上遍历个数
for k in range(1, nums[i] + 1):
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
return dp[bag_weight]22.打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
class Solution:
def rob(self, nums) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]23.打家劫舍II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
class Solution:
def rob(self, nums) -> int:
# 一是不偷第一间房，二是不偷最后一间房
if len(nums) == 1:
return nums[0]
val1 = self.robRange(nums[1:]) # 不偷第一间房
val2 = self.robRange(nums[:-1]) # 不偷最后一间房
return max(val1, val2)
def robRange(self,nums):
l = len(nums)
dp = [0] * l
dp[0] = nums[0]
for i in range(1, l):
if i == 1:
dp[i] = max(dp[i - 1], nums[i])
else:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]24.打家劫舍 III
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
class Solution:
def rob(self, root: TreeNode) -> int:
res = self.rob_tree(root)
return max(res[0], res[1])
def rob_tree(self, root):
if root is None:
return (0, 0) # (偷当前节点金额，不偷当前节点金额)
left = self.rob_tree(root.left)
right = self.rob_tree(root.right)
val1 = root.val + left[1] + right[1] # 偷当前节点，不能偷子节点
val2 = max(left[0], left[1]) + max(right[0], right[1]) # 不偷当前节点，可偷可不偷子节点
return (val1, val2)25.买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution:
def maxProfit(self, prices) -> int:
length = len(prices)
if length == 0:
return 0
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
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]26.买卖股票的最佳时机II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution:
def maxProfit(self, prices) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) # 注意这里是和121. 买卖股票的最佳时机唯一不同的地方
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
return dp[-1][1]27.买卖股票的最佳时机III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution:
def maxProfit(self, prices) -> int:
if len(prices) == 0:
return 0
dp = [[0] * 5 for _ in range(len(prices))]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, len(prices)):
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]
28.买卖股票的最佳时机IV
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution:
def maxProfit(self, k: int, prices) -> int:
if len(prices) == 0:
return 0
dp = [[0] * (2 * k + 1) for _ in range(len(prices))]
for j in range(1, 2 * k, 2):
dp[0][j] = -prices[0]
for i in range(1, len(prices)):
for j in range(0, 2 * k - 1, 2):
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i])
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i])
return dp[-1][2 * k]29.最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
class Solution:
def maxProfit(self, prices) -> int:
'''
状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
卖出股票状态，这里就有两种卖出股票状态
状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
状态三：今天卖出了股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
'''
n = len(prices)
if n == 0:
return 0
dp = [[0] * 4 for _ in range(n)]
dp[0][0] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
dp[i][2] = dp[i - 1][0] + prices[i]
dp[i][3] = dp[i - 1][2]
return max(dp[-1][3], dp[-1][2], dp[-1][1])30.买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
class Solution:
def maxProfit(self, prices, fee) -> int:
n = len(prices)
if n == 0:
return 0
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)
return max(dp[-1][0], dp[-1][1])