LeetCode 96 Unique Binary Search Trees
概述
https://leetcode.com/problems/unique-binary-search-trees/
动态规划法
拿到题目，第一反应可以根据第 n-1 的个数推断出 n 的个数。
仔细想了想，貌似挺麻烦的。
其实可以通过遍历一遍轮流作为根节点来解决问题。
class Solution {
public:
vector<int> dp;
int numTrees(int n) {
vector<int> dp(n+1, -1);
dp[0] = 1;
dp[1] = 1;
this->dp = dp;
return helper(n);
}
int helper(int n) {
if (dp[n] != -1) return dp[n];
int count = 0;
for (int i = 0; i < n; i ++) {
int ln = i - 0;
int rn = n - i - 1;
count += helper(ln) * helper(rn);
}
dp[n] = count;
return count;
}
};