题目描述
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
网友评论