动态规划 Leetcode 96 不同的二叉搜索树

不同的二叉搜索树

Leetcode 96

学习记录自代码随想录

要点：1.递推公式，想到以根节点数字不同作为分类条件求和得到dp[i]；

class Solution {
public:
    int numTrees(int n) {
        if(n == 1 || n == 2) return n;

        // 1.dp[i]返回输入i时的满足条件的二叉搜索树的种数
        vector<int> dp(n+1, 0);
        // 2.递推公式，想到以根节点不同作为分类条件求和得到dp[i]，dp[i] = sum(dp[j-1]*dp[i-j]) j = 1:1:n
        // 3.dp数组初始化
        dp[0] = 1;  // 不能设置为0，因为是乘积
        dp[1] = 1;
        dp[2] = 2;
        // 4.遍历顺序从小到大遍历
        for(int i = 3; i < n+1; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += (dp[j-1] * dp[i-j]);
            }
        } 
        // 5.举例推导dp数组
        return dp[n];
    }
};