leetcode

96.不同的二叉搜索树

力扣链接

动规五部曲

1. 确定用作状态转移的dp数组的下标及含义 n个节点有dp[n]个不同的二叉搜索树

2. 动规核心 状态转移方程/递推公式 i用来遍历从1到n，枚举所有以j为头结点个数的情况, 此时头结点j的左边有j-1个结点，右边有i-j个结点，以j为头结点有dp[j-1]* dp[i-j]个不同的二叉搜索树 对所有j<=n dp[i]+=dp[j-1]*dp[i-j]

3. dp数组如何初始化 空二叉树也是二叉搜索树 dp[0] = 1, 不用初始化dp[1]=1可由dp[0]算得
4. 确定遍历顺序 从小向大遍历<=n的所有整数i
5. 打印dp数组用于排错

class Solution {
public:
    int numTrees(int n) {
        // std::vector<int> dp(n+1)所有元素将被默认初始化为0 
        // 等价std::vector<int> dp(n+1,0);
        std::vector<int> dp(n+1);
        dp[0]=1;
        for (int i=1;i<n+1;i++)
            for (int j=1;j<=i;j++)
                //初始化时要全0因为在原dp[i]基础上+=
                dp[i]+=dp[j-1]*dp[i-j]; 
        return dp[n];
    }
};

This site is open source. Improve this page.