[Vssue]0096.不同的二叉搜索树.md

[youngyangyang04]

https://www.programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

[Du1in9]

int[] dp = new int[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];
    }
}
return dp[n];

// 例: n = 3, dp = [1,0,0,0]
i = 1:  j = 1: dp[1] += 1 * 1 (以 0 为头结点且 1 个节点有 1 种) = 1, dp = [1,1,0,0]
i = 2:  j = 1: dp[2] += 1 * 1 (以 1 为头结点且 2 个节点有 1 种) = 1
        j = 2: dp[2] += 1 * 1 (以 1 为头结点且 2 个节点有 1 种) = 2, dp = [1,1,2,0]
i = 3:  j = 1: dp[3] += 1 * 2 (以 2 为头结点且 3 个节点有 2 种) = 2
        j = 2: dp[3] += 1 * 1 (以 1 为头结点且 3 个节点有 1 种) = 3    
        j = 3: dp[3] += 2 * 1 (以 2 为头结点且 3 个节点有 2 种) = 5, dp = [1,1,2,5]

[BjtuDJP]

卡特兰数公式更好理解

[mockyd]

这种写法不会用到dp[0]，因为题目要求n>=1，但实际上就是dp[i] = dp[i - 1] * 2;这句取代了dp[0]的作用，与上述讲解中的方法区别不大 但我的推导过程是，由i作为结点时，只有左上和左下能放置子树，所以dp[i]的递推公式就是dp[左上方能出现的节点数] * dp[左下方能出现的节点数]，写成i、j的形式就一样了

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i ++) {
            dp[i] = dp[i - 1] * 2;
            for (int j = 1; j < i; j ++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }

        return dp[n];
    }
}