递归代码和动态规划代码相互转化

 二叉树的节点个数为n时，能返回多少种不同的二叉树结构

当n=0，只有一种结构，那就是空树

当n=1的时候，也只有一种结构

当n=2的时候，有两种结构

 当有n个节点时

（1） 除了根节点，其他n-1个节点全部在右子树上，如果F()函数可以求出n个节点可以有多少种二叉树结构，那么这种情况就有F（n-1)种结构

（2）左子树上有一个节点，其他n-2个节点全部在右子树上，如果F()函数可以求出n个节点可以有多少种二叉树结构，那么这种情况就有F（n-2)种结构

 （3）左子树上两个节点，右子树上n-3个节点，如果F()函数可以求出n个节点可以有多少种二叉树结构，那么这种情况就有F（2）+F（n-3)种结构

 .........

显然一种普遍的情况是，左子树上有i个节点，右子树上有n-i+1个节点，如果F()函数可以求出n个节点可以有多少种二叉树结构，那么这种情况就有F（i）+F（n-i+1)种结构

 所以有F（n)=F(0)+F(n-1）  + F(1)+F(n-2)   +.......+F(n-1)+F(0)

   public  int  f(int n)
    {
        if(n==0||n==1)   return 1;
        if(n==2)   return   2;
 
        int  result=0;
        for(int i=0;i<=n-1;i++)
        {
            int left=f(i);//左子树有多少种结构
            int right=f(n-i+1);//右子树有多少种结构
            result=result+left*right;
        }
        return  result;    
    }

改写成动态规划版本

    public int f(int n)
    {
        if(n<2)  return  1;
        int[]  dp=new int[n+1];
        //dp[i]表示i个节点可以形成多少种二叉树结构
        
        Arrays.fill(dp,0);
        
        dp[0]=1;
 
        //遍历dp数组，填满dp数组
        for(int i=0;i1;i++)
        {
            //对于dp数组里面的每一个值dp[i]，求解出来
            //左侧节点个数为j，右侧节点个数为i-j+1
            for(int j=0;j
            {
                dp[i]=dp[i]+dp[j]*dp[i-j+1];
            }
        }
        return dp[n];
    }