LetCode-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

Tree Dynamic Programming

집합이 비어 있으면 BST, 즉 빈 나무만 있습니다.
UniqueTrees[0] =1
컬렉션에 요소가 하나만 있는 경우 BST가 하나만 있는 단일 노드입니다.
UniqueTrees[1] = 1

Unique Trees[2] = Unique Trees[0] * Unique Trees[1] (1이 루트인 경우) + Unique Trees[1] * * Unique Trees[0] (2가 루트인 경우) + Unique Trees[1]+ Unique Trees[2]*Unique Trees[0](3이 뿌리인 경우) 따라서 관찰한 결과 Unique Trees의 추이 공식은 Unique Trees[i] = ∑ Unique Trees[0...k] * [i-1-k] k 수치 범위 0<=k <=(i-1)

'''
Created on Nov 13, 2014

@author:
ScottGu
'''
class

Solution
:

# @return an integer

def
numTrees(
self
, n):
        uniqueTrees={}
        uniqueTrees[
0
]=
1
        uniqueTrees[
1
]=
1


for
cnt
in
range(
2
, n+
1
):
            uniqueTrees[cnt]=
0

for
k
in
range(
0
, cnt):
                uniqueTrees[cnt]+=uniqueTrees[k]*uniqueTrees[cnt-
1
-k]


return
uniqueTrees[n]


if
__name__ ==
'__main__'
:
    sl=Solution()

print
sl.numTrees(
0
),
0

print
sl.numTrees(
1
),
1

print
sl.numTrees(
2
),
2

print
sl.numTrees(
3
),
3

print
sl.numTrees(
4
),
4

print
sl.numTrees(
5
),
5

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[leetcode]_Validate Binary Search Tree

제목: 두 갈래 나무 한 그루가 합법적인지 판단한다.두 갈래 트리가 왼쪽 트리의 모든 값생각: 1. 현재 루트 노드에서 판단하여 루트 노드의 왼쪽 트리 최대값 maxLeft, 오른쪽 트리 최소값 minRight를 구...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

LetCode-Unique Binary Search Trees [동적 계획]

좋은 웹페이지 즐겨찾기