动态规划专题之--- Unique Binary Search Trees

怼烎@ 2022-05-16 13:23 182阅读 0赞

*   *  1.分解子问题
     *  2.确定状态
     *  3.确定初始状态
     *  4.确定状态转移方程

[题目链接][Link 1]  
[参考博文][Link 2]

表示根本不知道什么是卡特兰数，百度的截图  
![image\_1bdeqri3b18kp29b1npl1btol759.png-13kB][image_1bdeqri3b18kp29b1npl1btol759.png-13kB]

根据动态规划解题步骤慢慢分析

## 1.分解子问题 ##

根据题意分析，二叉搜索树不同原因在于。一个数列中的所有元素都可以成为祖先。  
于是第一个子问题是每个数都可以作为祖先。我们可以遍历数列。

然后确定一个数为祖先后，剩下n-1个数先分为两拨，而这两拨如何分？左子树节点数从0开始一直到某个临界值时，这样过一遍就是完美了。

于是左子树的子树又可以根据这样的递推关系继续往下面分。

当祖先（根为数值为i时），左子树最大的数为i-1。于是左子树的元素个数可以从0增加到i-1。而右子树的节点个数也可以依次增多。

![image\_1bdescqft3uo1t8v60r8ad7e9.png-17.9kB][image_1bdescqft3uo1t8v60r8ad7e9.png-17.9kB]

这里的n=3，不是说的根节点数字为3，而是说的当节点数为3的时候

## 2.确定状态 ##

dp\[i\]=j 表示当有i的节点时，BST的种类数目。

## 3.确定初始状态 ##

`dp[0]=1`; 没有节点只有一种情况，空树  
`dp[1]=dp[0]*dp[0]=1`; 只有一个节点也是只有一种情况

## 4.确定状态转移方程 ##

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

模拟一下输入3的情况

<table> 
 <thead> 
 <tr> 
 <th>i</th> 
 <th></th> 
 <th></th> 
 <th></th> 
 <th></th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>i=1</td> 
 <td>dp[1]=dp[0]&amp;#x2217;dp[0]” role=”presentation” style=”position: relative;”&gt;dp[1]=dp[0]∗dp[0]dp[1]=dp[0]∗dp[0]</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>i=2</td> 
 <td>dp[2]=dp[1]&amp;#x2217;dp[0]” role=”presentation” style=”position: relative;”&gt;dp[2]=dp[1]∗dp[0]dp[2]=dp[1]∗dp[0]</td> 
 <td>dp[2]=dp[0]&amp;#x2217;dp[1]” role=”presentation” style=”position: relative;”&gt;dp[2]=dp[0]∗dp[1]dp[2]=dp[0]∗dp[1]</td> 
 <td></td> 
 <td></td> 
 </tr> 
 <tr> 
 <td>i=3</td> 
 <td>dp[3]=dp[2]&amp;#x2217;dp[0]” role=”presentation” style=”position: relative;”&gt;dp[3]=dp[2]∗dp[0]dp[3]=dp[2]∗dp[0]</td> 
 <td>dp[3]=dp[1]&amp;#x2217;dp[1]” role=”presentation” style=”position: relative;”&gt;dp[3]=dp[1]∗dp[1]dp[3]=dp[1]∗dp[1]</td> 
 <td>dp[3]=dp[0]&amp;#x2217;dp[2]” role=”presentation” style=”position: relative;”&gt;dp[3]=dp[0]∗dp[2]dp[3]=dp[0]∗dp[2]</td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1. i=1 表示只有一个节点的情况  
2. i=2 表示两个节点的情况，这个时候就可以利用`case1`中计算出来的结果`dp[1]`了。  
3. i=3 表示三个节点的情况，这个时候就可以利用`case2`中计算出来的结果了。

**对应i=3的时候**  
![image\_1bdesri85133m1l1811i21tlp16rm.png-109.7kB][image_1bdesri85133m1l1811i21tlp16rm.png-109.7kB]

public class Solution{
 
 public int numTrees(int n){
 if(n==0||n==1){
 return 1;
 }
 int []dp=new int[n+1];
 //每个数都可以做根节点，相当于有这么多个节点时
 for(int i=1;i<=n;i++){
 
 //i为根节点时，左子树从0开始增加
 for(int j=0;j<i;j++){
 dp[i]+=dp[j]*dp[i-j-1];
 }
 }
 return dp[n];
 }
 
 }
 
 
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18

![image\_1bdetejv91u6a1a6k3fo1vo2q9113.png-20.9kB][image_1bdetejv91u6a1a6k3fo1vo2q9113.png-20.9kB]

[Link 1]: https://leetcode.com/problems/unique-binary-search-trees/#/description
[Link 2]: http://www.cnblogs.com/hewx/archive/2015/05/26/4530439.html
[image_1bdeqri3b18kp29b1npl1btol759.png-13kB]: /images/20220516/ab98faa665c74e548aca4b34dc8f672a.png
[image_1bdescqft3uo1t8v60r8ad7e9.png-17.9kB]: /images/20220516/9de911372146494ca9ed52fa102bbe6b.png
[image_1bdesri85133m1l1811i21tlp16rm.png-109.7kB]: /images/20220516/20c84bf9532e4cdd9a9a2fb9652df5e4.png
[image_1bdetejv91u6a1a6k3fo1vo2q9113.png-20.9kB]: /images/20220516/c9c3a2844f0c4198a0bf4f76633fd4cd.png