96 - Unique Binary Search Trees

#medium

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 = 3
Output: 5

Example 2:
Input: n = 1
Output: 1

https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

class Solution {
public:
    int numTrees(int n) {
        // dp[i] i個不同種樹所有情況相加
        vector<int> dp( n + 1 );
        dp[0] = 1; // 空樹也是一種狀況
        for ( int i = 1; i <= n; i++ ) {
            for( int j = 1; j <= i; j++ ) {
                dp[i] = dp[i] + ( dp[j-1] * dp[i-j] );
            }
        }

        return dp[n];
    }
};

有i個節點，以j為頭節點，左邊為j-1個，右邊為i-j個(右邊比左邊大)。
那麼遍歷i裡面每一個數作為頭結點的狀態，用j來遍歷。
樹頭為i，左邊j-1 為j為頭結點左子樹節點數量，i-j 為以j為頭結點右子樹節點數量。