代码看着行数很少,其实思路不好想
- dp数组含义:下表i表示i个不同元素,dp[i]表示二叉搜索的数目
- 递推公式:dp[i] = dp[0]*dp[i-1] + dp[1] * dp[i-2] ......dp[i-2] * dp[1] + dp[i-1]*dp[0]
- dp数组初始化:dp[0] =1 ,dp[1] =1
- 遍历顺序:从前向后遍历
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param n int整型 * @return int整型 */ int BSTCount(int n) { // write code here vector<int> dp(n+1);//dp数组含义 dp[0] =1;dp[1] =1;//初始化dp数组 for (int i=2; i<n+1; i++) {//从前向后遍历 for (int j=0; j<i; j++) { dp[i] += dp[j] * dp[i-1-j];//递推公式 } } return dp[n]; } };