[数据结构与算法]96. 不同的二叉搜索树 (动态规划)

状态转移方程递推

class Solution {
    public int numTrees(int n) {
        // 创建一个一维数组,存放二叉树节点
        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];
    }
}

心静思远30up的视频