leetcode
a few seconds 读完 (大约 99 个字) 0次访问

LeetCode 刷题记录: 96. Unique Binary Search Trees [Python]

原题

https://leetcode.com/problems/unique-binary-search-trees/

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

思路

对于n个值，以i为根，则可以将[1,i-1]放入左边，[i+1,n]放入右边，因此有[i-1]*[i-j]种方式。

代码

1
2
3
4
5
6
7
8
class Solution:
    def numTrees(self, n: int) -> int:
        arr=[0]*(n+1)
        arr[0]=1
        for i in range(1,n+1):
            for j in range(1,i+1):
                arr[i]+=arr[j-1]*arr[i-j]
        return arr[-1]
#

喜欢这篇文章？打赏一下作者吧

LeetCode 刷题记录: 85. Maximal Rectangle [Python]
LeetCode 刷题记录: 98. Validate Binary Search Tree [Python]

评论

关注我

分类

标签

Backtrack 1
Binary 1
DFS 2
Dynamic Programming 1
GTD 1
Greedy 1
Hashmap 1
LeetCode 17
LinkedList 1
Manacher's Algorithm 1
Premutation 1
Tricky 1
Triky 1
app 1
framework 1
games 1
hexo 1
java 2
php 1
site 2

最新文章

归档

最新文章

归档

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×