[Leetcode][第96题][JAVA][不同的二叉搜索树][动态规划][数学]

迷南。 2023-02-26 09:26 5阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 动态规划 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
第 1 步：设计状态  
![在这里插入图片描述][20200715091954660.png]  
第 2 步：状态转移方程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]![在这里插入图片描述][20200715092131912.png]  
第 3 步：考虑初始化  
![在这里插入图片描述][2020071509213818.png]  
第 4 步：考虑输出  
![在这里插入图片描述][20200715092145839.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]

**时间复杂度：O(N^2) 空间复杂度：O(N)**  
![在这里插入图片描述][20200715092241584.png]

public int numTrees(int n) { 
            int[] G = new int[n + 1];
            G[0] = 1;
            G[1] = 1;
    
            for (int i = 2; i <= n; ++i) { 
                for (int j = 1; j <= i; ++j) { 
                    G[i] += G[j - 1] * G[i - j];
                }
            }
            return G[n];
        }

###### 2. 数学公式 ######

![在这里插入图片描述][20200715092615322.png]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200715092626863.png]

public int numTrees(int n) { 
            // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
            long C = 1;
            for (int i = 0; i < n; ++i) { 
                C = C * 2 * (2 * i + 1) / (i + 2);
            }
            return (int) C;
        }

#### 【总结】 ####

###### 1. 动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2.卡塔兰数 Cn ######

![在这里插入图片描述][20200715092840116.png]

###### 3.二叉树 找规律 动态规划 画图递归 ######

转载链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/54a46e5c013e4dd987c4b8094f16ce41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/ce0f9eb39eb7448c9ab6f3436e8fd25d.png
[20200715091954660.png]: /images/20230209/04425e608bff452489af11ff8f16d2a0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020071509222242.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200715092131912.png]: /images/20230209/728420aba4ad470f83d0cfcda8bf6ef3.png
[2020071509213818.png]: /images/20230209/ed4f2071b73542bd8316afd63641fd14.png
[20200715092145839.png]: /images/20230209/b9bef489a1194c50966158f1d6cfa02d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20230209/05a8029d0930467382eec603c2c5602c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: /images/20230209/abdec4bfc5c94ee0b691072b911d2f09.png
[20200715092241584.png]: /images/20230209/e35a13345aea47e6942f3cc4bb3889e6.png
[20200715092615322.png]: /images/20230209/dc277331bc5a4e2fb529391f3b15f485.png
[20200715092626863.png]: /images/20230209/5483544510e1454290cf18db46acdddc.png
[20200715092840116.png]: /images/20230209/59ad94a409fb4b76ae7a2b5536cf0903.png