题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/last-stone-weight-ii

343 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

class Solution:def integerBreak(self, n: int) -> int:#dp[i]表示 拆分数值为i时可以获得的最大乘积#递推关系 dp[i]={for j in range(0,i)max(j*(i-j))}#初始化#遍历顺序#打印dp=[0]*(n+1)dp[2]=1for i in range(3,n+1):for j in range (1,i-1):dp[i]=max(dp[i],max(dp[i-j]*j,j*(i-j)))return dp[n]

96 不同二叉树搜索

class Solution:def numTrees(self, n: int) -> int:#dp[i]表示节点数为i的二叉搜索树的形态# 递推公式for j in range(i) dp[i]=dp[i]+dp[j]*dp[i-j-1]dp=[0]*(n+1)dp[0]=1dp[1]=1for i in range(2,n+1):for j in range(0,i):dp[i]=dp[i]+dp[j]*dp[i-j-1]return dp[n]

0-1背包问题
416 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution:def canPartition(self, nums: List[int]) -> bool:#0-1背包是从物品中拿物品使得在满足背包容量的前提下，value最大#这题类似 数字代表物品每个数字拿或者不拿 满足和相等这一条件#dp[j]表示和为j #两个子集和相等#递推关系dp[j]= dp[j]=max(dp[j],dp[j-weight[i]]+value[i])sum_=sum(nums) if (sum_%2==1):return Falsedp=[0]*int(sum_//2+1)for i in range(len(nums)):for j in range(sum_//2,nums[i]-1,-1):dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])if dp[sum_//2]==sum_//2:return Trueelse:return False

1049 最后一块石头的重量
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:# 类似01背包，stone为价值也是weight 石头是物品 选或者不选 # 尽可能的满足背包容量 #dp[i]表示第i回合 石头的重量#递推关系 for j in( ) dp[i]=max()target=sum(stones)//2dp=[0]*int(target+1)for i in range(len(stones)):for j in range(target,stones[i]-1,-1):dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])return sum(stones)-dp[target]-dp[target]

0-1背包问题 好有学问 明天再学学