algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-b16de/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-b16de/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！第 21 期打卡挑战 (https://opedk.xet.tech/s/4ptSo2) 最后几天报名！ 读完本文，你不仅学会了算法套路，还可以顺便解决...

https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-b16de/

[lostinthee]

96题不是很明白为啥basecase是lo > hi ？为什么不是lo = hi？

[bhfykx]

i = lo时， 就是count(lo, lo - 1)，已经不满足lo == hi了

[shiboys]

这篇文章确实有点费解！

[zjfjack]

讲道理95题也还是可以用memo的 毕竟每次都new了一个root

[petercdcn]

没明白这里为什么是double for loop？为什么不能两个单独的 loop？ 一个做了 left tree；一个做right tree？
// 3、给 root 节点穷举所有左右子树的组合。
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {

我的第一直觉是：
for (TreeNode left : leftTree) {
...
for (TreeNode right : rightTree) {
...
为什么不能分别去做左右树呢？

[yeyang521]

第一题在lc上找了个便于理解的, 思路是一样的 ,对比了发现区间其实就是元素的数量. lo hi给我看迷糊了

Map<Integer, Integer> map = new HashMap<>();

public int numTrees(int n) {
    //如果只有0，或者1个节点，则可能的子树情况为1种
    if (n == 0 || n == 1){
        return 1;
    }

    if (map.containsKey(n)){
        return map.get(n);
    }

    int count = 0;
    for (int i = 1; i <= n; i++) {
        //当用i这个节点当做根节点时

        //左边有多少种子树
        int leftNum = numTrees(i-1);

        //右边有多少种子树
        int rightNum = numTrees(n-i);

        //乘起来就是当前节点的子树个数
        count+=leftNum*rightNum;
    }

    map.put(n,count);

    return count;
}

[CZT0]

95题 golang DP自底向上解法（原答案超时）

func numTrees(n int) int {
    // 当 n 小于或等于 1 时，只有一种结构的二叉搜索树
    if n <= 1 {
        return 1
    }

    // 初始化一个切片 dp，用于存储从 0 到 n 的不同二叉搜索树数量
    dp := make([]int, n+1)
    // dp[0] 和 dp[1] 都是 1，因为没有节点或只有一个节点的树只有一种形态
    dp[0], dp[1] = 1, 1

    // 外层循环，遍历所有的节点数（从 2 到 n）
    for nodes := 2; nodes <= n; nodes++ {
        // 内层循环，遍历所有可能的根节点位置
        for root := 1; root <= nodes; root++ {
            // 计算左子树和右子树的节点数
            left := root - 1   // 左子树的节点数
            right := nodes - root // 右子树的节点数

            // 对于每个根节点位置，不同的二叉搜索树的数量等于左子树的数量乘以右子树的数量
            dp[nodes] += dp[left] * dp[right]
        }
    }
    // 返回由 n 个节点组成的不同二叉搜索树的数量
    return dp[n]
}