二叉搜索树的个数和枚举(DP)(vector copy)

96. Unique Binary Search Trees.cpp

/*My naive solution...only beats 0.6% of people...
因为..因为有好多numTrees(n)都重复算了...
所以把这个改成DP的话应该就可以加快不少时间
*/
class Solution {
public:
    
    int numTrees(int n) {
        int r = 0;
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        for (int i=0;i<n-2;i++){
            r += numTrees(n-i-2)*numTrees(i+1);
        }
        r += 2*numTrees(n-1);
        return r;
    }
};

Dynamic-Programming.cpp

class Solution {
public:
    
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        
        if (n==0) return 0;
        if (n==1) return 1;
        if (n==2) return 2;
        
        for (int x=3;x<=n;x++){
            for (int i=0;i<x;i++){
                dp[x] += dp[x-1-i]*dp[i];
            }
            cout << dp[x] << " ";
        }
        
        return dp[n];
    }
};

gistfile1.txt

/*
如何把一个vector的值一个一个复制到一个新个vector里面？
*/

给你一个整数n，找出所有BST(Binary Search Trees)的个数。并枚举。BST是右子节点大于根，左子节点小于根。