题目描述

https://leetcode-cn.com/problems/unique-binary-search-trees/

代码

是个dp哦，自己独立写出来的，找到了递推公式。但是实现的丑一些，一会咱贴个写的优雅的答案，和一个解释的很清楚的视频。

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

结论

这个就是求n的卡特兰数。
优雅点的实现：https://www.cnblogs.com/grandyang/p/4299608.html

视频讲解：https://www.youtube.com/watch?v=GgP75HAvrlY