[leetcode]Unique Binary Search Trees @ Python
2024-10-08 00:31:03
原题地址:https://oj.leetcode.com/problems/unique-binary-search-trees/
题意:
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解题思路:这题从数学上讲,其实是卡特兰数。不过我们显然不从数学上来解决这个问题。这题是求二叉树的棵数。这里有个解题技巧:一般来说求数量,要首先想到使用动态规划(dp),而如果是像下一题的要求,不只是数量,还要把所有的树都枚举出来,就要使用dfs(深度优先搜索)来遍历决策树了。
那么这道题是使用动态规划来解决的。那么如何去求这个问题的状态转移方程呢?其实大部分动态规划的难点都是求状态转移方程。n=0时,为空树,那么dp[0]=1; n=1时,显然也是1,dp[1]=1;n=2时,dp[2]=2; 对于n>2时,dp[n]=dp[0]*dp[n-1]+dp[1]*dp[n-2]+......+dp[n-1]*dp[0];这不就是卡特兰数的定义吗?编程很容易实现。
代码:
class Solution:
# @return an integer
def numTrees(self, n):
dp = [1, 1, 2]
if n <= 2:
return dp[n]
else:
dp += [0 for i in range(n-2)]
for i in range(3, n + 1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
最新文章
- ASP.NET Web API 简介
- Secure Socket Tunneling Protocol Service服务无法启动(win7)
- CInternetSession CHttpFile Post提交数据
- Android类库打包方法探究
- Redis常用数据类型
- android应用程序的优先级
- 用maven来创建web工程
- 《Go in action》读后记录:Go的并发与并行
- 网络协议 20 - RPC 协议(上)- 基于XML的SOAP协议
- 使用IO流写文件的一些骚操作
- springboot项目打成war包
- 虚拟机vbox
- linux 关于时间日期date
- Scala工具库
- 穷竭搜索:POJ 3187 Backward Digit Sums
- java 调用静态方法和构造函数和静态块执行的先后顺序
- 苹果的 Metal 工程
- leetcode-695-Max Area of Island(BFS)
- sql中的制表符、换行符、回车符,问题
- hbase 预分区
热门文章
- android studio svn 创建分支
- SDOI2013 R1 Day2
- 【莫队算法】【权值分块】bzoj3920 Yuuna的礼物
- 【BZOJ-1913】signaling信号覆盖 极角排序 + 组合
- hdu 5828 Rikka with Sequence 线段树
- Ulipad安装、配置使用教程(附Ulipad下载)
- Java中的锁(转)
- LPC43xx State Configurable Timer : SCT
- STM32 TIMER DIAGRAM
- Linux网络编程socket选项之SO_LINGER,SO_REUSEADDR