343. 整数拆分
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0] * (n + 1)
dp[1] = 1
for i in range(1, n + 1):
for j in range(1, n//2 + 1):
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return dp[n]
【思考】
1. max(dp[i], j * (i - j), j * dp[i - j]) 含义：
dp[i]是循环到 j 时，j-1时的dp[i] 值；
i*(i - j) 即 分成俩数；
j * dp[ i - j ] 即分成3个及以上的数。
2. for j in range(1, n//2 + 1): 拆分的时候，不需要 j 把 i 全部遍历一遍，如i = 5，j只要取1,2即可，即1*4,2*3，如果取3*2就重复了。
96.不同的二叉搜索树
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n + 1) # 创建一个长度为n+1的数组，初始化为0
dp[0] = 1 # 当n为0时，只有一种情况，即空树，所以dp[0] = 1
for i in range(1, n + 1): # 遍历从1到n的每个数字
for j in range(1, i + 1): # 对于每个数字i，计算以i为根节点的二叉搜索树的数量
dp[i] += dp[j - 1] * dp[i - j] # 利用动态规划的思想，累加左子树和右子树的组合数量
return dp[n] # 返回以1到n为节点的二叉搜索树的总数量【思考】难题。