题解 | #不同的二叉搜索树(一)#

代码看着行数很少，其实思路不好想

• 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];
    }
};