title: LEETCODE-DAY41
date: 2024-04-01 18:58:14
tags:
今日内容：343. 整数拆分、96.不同的二叉搜索树
T1
class Solution:
def integerBreak(self, n: int) -> int:
dp=[0 for i in range(59)]
dp[2]=1
dp[3]=2
dp[4]=4
dp[5]=6
dp[6]=9
for i in range(7,max(7,n)+1):
dp[i]=3*dp[i-3]
return dp[n]
AC
简单的数论问题
首先一定得拆成素数的乘积
其次对于素数5=2+3，2*3=6>5
其他大于5的素数可同样推导
故最终一定拆分为只含2和3的乘积才能达到最大
显然n>=7后满足递推（n=6不满足是因为dp[3]!=3）
T2
class Solution:
def numTrees(self, n: int) -> int:
dp=[0 for _ in range(20)]
dp[0]=1
dp[1]=1
dp[2]=2
for i in range(3,max(3,n)+1):
for j in range(1,i+1):
dp[i]+=dp[j-1]*dp[i-j]
return dp[n]
AC
按根节点值分类，数组[1,2…,i]当根节点值为j时，其左右子树分别为dp[j-1]和dp[i-j]个
