LeetCode_96. Unique Binary Search Trees

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

Unique Binary Search Trees - LeetCode

Solution1. 

 

Input N에 대해서 1~N에 대해서 루트일 경우는,

 

root node가 1일 경우 :  [왼쪽 자식] null F(0), [오른쪽 자식] N-1 case --> F(N-1)

root node가 2일 경우 :  [왼쪽 자식] F(1),      [오른쪽 자식] N-2 case --> F(N-2)

root node가 3일 경우 :  [왼쪽 자식] F(2),     [오른쪽 자식] N-3 case --> F(N-3)

root node가 4일 경우 :  [왼쪽 자식] F(3),     [오른쪽 자식] N-4 case --> F(N-4)

.

.

.

.

root node가 n-1일 경우 : [왼쪽 자식] F(N-2),    [오른쪽 자식] F(1)

root node가 n일 경우 :    [왼쪽 자식] F(N-1),    [오른쪽 자식] F(0)

 

따라서 F(N) = F(0) * F(N-1) + F(1) * F(N-2) + ...... + F(N-2) * F(1) + F(N-1) * F(0) 로 표현이 가능

 

class Solution:
    def numTrees(self, n: int) -> int:
        table = [0]*(n+1)
        table[0] = table[1] = 1
        
        # F(2) ~~ F(N) 까지 update
        for i in range(2, n+1):
            total = 0
            # table[i] = table[0]*table[i-1] + table[1]*table[i-2] + ... + table[i-1]*table[0]
            for j in range(1, i+1):
                total += (table[j-1] * table[i-j])
            table[i] = total
            
        return table[n]