动态规划（C++）

leecode解法
看了一下了leecode的解法 (https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/)

我觉得和有意思：
取有序数列中某节点为i（作为根节点）,这时把树分成了两部分左子树NUM( i - 1 )和右子树NUM( n-i ) , ( NUM( x ) 为不同左右子树的数量 )。设二叉搜索树的个数为 F( i , n )，则 F( i , n ) = NUM( i - 1 ) * NUM( n - i ) 不同的二叉搜索树的总数 NUM( n )，是对遍历所有 i( 1 ≤ i ≤ n ) 的 F( i , n ) 之和，所以NUM( n ) = 累加F( i , n ),可以推得：NUM( n ) = 累加 NUM( i - 1 ) * NUM( n - i );

#include<iostream>
#include<vector>
using namespace std;

int number_binary(int num){
    if(num < 2) return num;
     vector<int> NUM(num + 1, 0);
     NUM[0] = 1;
     NUM[1] = 1;

     for (int i = 2; i <= num; ++i) {
         for (int j = 1; j <= i; ++j) {
            NUM[i] += NUM[j - 1] * NUM[i - j];
         }
     }
    return NUM[num];
}

int main(){
    int num; 
    cin >> num;
    cout << number_binary(num) << endl;
}