【力扣】刷题备忘录-动归-96. 不同的二叉搜索树

2023-12-15 00:28:20

96. 不同的二叉搜索树
这个解法属于那种,想不到就难,知道了就豁然开朗那种。
只要想到其实一棵树的可能数量 = 左子树的可能数量 × 右子树的可能数量。算法就基本没难度了。
详细讲解逻辑可以看:代码随想录的视频链接, 我这里就不赘述了。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] = 1;
        for (int i  = 1; i <= n; i++){
            for (int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
                // std :: cout << "i的当前值是:" << i << std :: endl;
                // std :: cout << "dp i的当前值是:" << dp[i] << std :: endl;
            }
        }
        return dp[n];
    }
};

文章来源:https://blog.csdn.net/weixin_42735060/article/details/134907037
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。