動機

當成range，就可以去二分了

Problem

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

 

Example 1:

Input: n = 3Output: 5

Example 2:

Input: n = 1Output: 1

 

Constraints:

  • 1 <= n <= 19

Sol

分成左右兩邊，如果範圍長度只有1就是一個node，非法範圍就是沒node，但這兩個都是一個組合數

class Solution:
    def numTrees(self, n: int) -> int:
        @cache
        def dp(i,j):
            if i >= j or j-i == 1: # single node or empty node
                return 1
            else:
                return sum([dp(i,k) * dp(k+1,j) for k in range(i,j)])
        return dp(1,n+1)