96. 不同的二叉搜索树

96. 不同的二叉搜索树

1.想法

image.png

当根确定后,就是左右两边的子树的排列,这个过程相当于在处理前面处理过的结构,例如图中的n=3时,左子树分配两个,右子树分配0个,那么就相当于处理n=2的情形,而且我们发现当根为3的时候和n=2一模一样,但是当根为1时,其处理过程与n=2类似
那么我们可以得出结论我们处理过程就是一个给左右子树选择节点个数的过程,以左子树为例,其取节点个数可以从0->n-1,相应的右子树个数为n-1->0
1.备忘录算法:
我们用一维数组f[]表示我们的结果,那么f[n]代表了当取值n的时候的结果
f[n]=f(i)*f(n-i-1)
当f(i)不知道时,先去求子问题f(i)的值

优化

我们发现对于一个数来说,例如3,我们只需计算以1为底的值,那么以3为底的值我们也就知道了,而对于以二为底的我们需要单独计算,放到特征值里面,那么就是说左子树为节点为0或者1计算完毕就行了,其最终结果为
1.若为偶数f(n)=2f(i)f(n-i-1) //计算左边从分0-(n/2-1)个节点的值,右边会经历相同的变化,所以不用重复计算乘以2为最终结果
2.若为奇数f(n)=2f(i)f(n-i-1) +f(n/2)f(n/2) //计算从0-(n/2-1),但是n/2的值没有计算,其等于f(n/2)f(n/2)左右各n/2各节点,各有f(n/2)种变化

2.动态规划

与备忘录自顶向下的算法不同,动态规划是自底向上,所以需要先计算前面的子问题,再通过前面的子问题计算现在的问题
规约公式还是:
f[n]=f(i)*f(n-i-1)

2.代码:

1.备忘录算法(无优化):

public int numTrees(int n) {
       if(n==1)return 1;  
       int[] f = new int[n+1];
       f[1]=1;
       f[0]=1;
       f[n] = caculateNum(f,n);  //先去计算原问题
       return f[n];
    }

    private int caculateNum(int[] f, int n) {
        for(int i=0;i<n;i++){
            if(f[i] == 0){  //如果子问题没有解的话,先去解决子问题
                f[i]=caculateNum(f,i);   
            }
            if(f[n-i-1]==0){
                f[n-i-1]=caculateNum(f,n-i-1);
            }
            f[n]+=f[i]*f[n-i-1];  //根据子问题求出原问题
        }
        return f[n];
    }

image.png

2.备忘录算法(优化)

 public int numTrees(int n) {
       if(n==1)return 1;  
       int[] f = new int[n+1];
       f[1]=1;
       f[0]=1;
       f[n] = caculateNum(f,n);
       return f[n];
    }

     private int caculateNum(int[] f, int n) {
        for(int i=0;i<n/2;i++){    //不用计算所有的值,而是计算前一半的
            if(f[i] == 0){
                f[i]=caculateNum(f,i);
            }
            if(f[n-i-1]==0){
                f[n-i-1]=caculateNum(f,n-i-1);
            }
            f[n]+=f[i]*f[n-i-1];
        }
        return n%2==0?f[n]*2:(f[n]*2+f[n/2]*f[n/2]);
    }

image.png

3.动态规划算法

public int numTrees(int n) {
       if(n==1)return 1;
       int[] f = new int[n+1];
       f[1]=1;
       f[0]=1;
       for(int i=2;i<=n;i++){   //先计算子问题,然后再计算原问题
           for(int j=0;j<i/2;j++){
               f[i]+=f[j]*f[i-j-1];
           }
           f[i] = ((i%2==0) ? (f[i]*2) :(f[i]*2+f[i/2]*f[i/2])); 
       }
       return f[n];
   }