96. 不同的二叉搜索树 - 力扣(LeetCode)
思路:
- dp[i]含义:从 1 到 i 互不相同的二叉搜索树有多少种
- 递推公式:dp[i]=dp[i]+dp[j-1]*dp[i-j] ( j 从 1 到 i )
- 初始化:dp[0]=1
- 遍历顺序:从前往后
class Solution(object):
def numTrees(self, n):
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
for j in range(1,i+1):
dp[i]+=dp[j-1]*dp[i-j]
return dp[n]