【Leetcode刷题Python】96. 不同的二叉搜索树
1 题目
给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3
输出:5
示例 2:
输入:n = 1
输出:1
2 解析
状态:当前i为根节点,n个不同的数组成的二叉搜索数的个数,表示为dp[i]
假设 i = 5
- 当根节点等于 1 时 ,其余数字都比1大,只能在右边 dp[1] += dp[4]
- 当根节点等于 2 时,左边有一个1比2小,右边有三个比2大的数字 dp[2] += dp[1] * dp[3]
- 当根节点等于 3 时,左边有两个数比3小,右边有两个数比3大的数字 dp[3] += dp[2] * dp[2]
- 知道根节点等于5,左边有4个数字比5小,只能放在5的左边,dp[5] += dp[4]
推理出,状态转移方程,当有n个节点数,每个节点i的状态为
d
p
[
i
]
=
d
p
[
i
−
1
]
∗
d
p
[
n
−
i
]
dp[i] = dp[i-1]*dp[n-i]
dp[i]=dp[i−1]∗dp[n−i]
d
p
[
0
]
=
1
,
d
[
1
]
=
1
dp[0]=1, d[1] = 1
dp[0]=1,d[1]=1
3 python实现
class Solution:
def numTrees(self, n: int) -> int:
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2,n+1):
for j in range(i+1):
dp[i] +=dp[j-1]*dp[i-j]
return dp[n]
相关文章
- python识别文字位置_如何利用Python识别图片中的文字
- python进制转换函数-Python中进制转换函数的使用
- python jieba库_Python jieba库的使用说明「建议收藏」
- 用python来开发webgame服务端(1)[通俗易懂]
- java与python-如何对比Python和Java,只需三分钟告诉你!
- 【说站】python中Qt是什么
- Python保存json_python保存json文件
- python设置时间过期改变状态_Python Redis设置过期时间「建议收藏」
- python读取excel文件代码_python怎么加速读取excel
- Python将数据写入txt文件_python将内容写入txt文件
- 【测试开发】python系列教程:Python 推导式
- 【测试开发】python系列教程:Python 运算符
- python(五)
- python TCP服务器v1.8 - PyQt5登录界面美化+淡入淡出
- 使用 Python 开发桌面应用程序的最佳方法是什么?
- Linux系统如何运行Python脚本(linux执行python脚本)
- Python函数式编程(map()、filter()和reduce())详解
- 如何创建Python程序包,Python程序包结构详解(超级详细)
- Python重载运算符实现自定义序列
- Linux环境下安装Python(linux装python)
- python使用Python轻松操作Redis(redis-)
- Python玩转Redis:提升缓存效率(python使用redis)
- Python类的基础–设计、使用
- 使用Python连接MySQL数据库,实现高效数据交互(python连接mysql)
- 在Python中简单调用MySQL(python调用mysql)