DP：动态规划之一起来数二叉树

蔚落 2023-10-07 12:14 4阅读 0赞

## DP：动态规划之一起来数二叉树 ##

### 题目： ###

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

### 思路： ###

DP的核心是求出递推方程  
可用二维数组保存计算结果  
对于含i个节点，j个叶子节点的二叉树(j<=i)，设总形态数为a\[i\]\[j\]  
将含i个节点，j个叶子节点的二叉树分为两部分，一部分为左子树，另一部分为右子树  
设右子树包含x个节点，y个叶子节点；则左子树包含i-x-1个节点，j-y个叶子节点；0<=x<=i-1,0<=y<=j  
**递推方程**：  
![在这里插入图片描述][20200406152626413.png]  
**初始条件**:

ans[51][51]={
        };
    ans[0][0]=1;
    ans[1][1]=1;

ans\[0\]\[0\]表示树为空  
ans\[1\]\[1\]表示树只含一个节点  
上述两种情况的形态数均为1

--------------------

使用这种方法直接将表算出来，会存在一定的时空间效率损失，但可不进行记忆化，因为这种损失程度并不大

--------------------

### 代码： ###

#include <stdio.h>
    #define mod 1000000007
    long long ans[51][51]={
        };
    int main()
    {
        
    
    	ans[0][0]=1;
    	ans[1][1]=1;
    	int i;
    	int j;
    	int x;
    	int y;
    	for( i=2;i<=50;i++ )
    		for( j=1;j<=i;j++ )
    			for( x=0;x<=i-1;x++ )
    				for( y=0;y<=j;y++ )
    					ans[i][j]=( ans[i][j]+ans[i-x-1][j-y]*ans[x][y] )%mod;
    	int n;
    	int m;
    	while( scanf( "%d %d\n",&n,&m )==2 )
    	{
        
    		printf( "%lld\n",ans[n][m] );
    	}	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200406144807404.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[20200406144850651.png]: https://img-blog.csdnimg.cn/20200406144850651.png
[20200406152626413.png]: https://img-blog.csdnimg.cn/20200406152626413.png