HDU 4359-Easy Tree DP?-动态规划-递归方法实现

实现原理：http://www.acmerblog.com/hdu-4359-easy-tree-dp-7370.html。下面用递归的方法实现：

//为保证递归深度不是太大，取值尽量取小些

#include<iostream>

using namespace std;

typedef	unsigned int		uint32;
typedef	unsigned short int	uint16;
		
//得到组合系数的值，从n个元素中选出m个元素的组合数
uint32 binomial_coefficient(unsigned int n, unsigned int m)
{
	if ((n-m) < m)
	{
		m = n - m;
	}
	
	if (n < m)
	{		
		return 0;
	}
	
	if (0 == m)
	{
		return 1;
	}	
	uint32 temp1 = binomial_coefficient(n-1, m);
	uint32 temp2 = binomial_coefficient(n-1, m-1);
	
	return (temp1 + temp2);
}

uint32 func(uint16 i, uint16 j)
{	
	if ((0 == j) || (0 == i))
	{
		return 0;
	}

	if (1 == i)
	{
		return 1;		//注意func(1,j) = 1(j>=1)
	}

	uint32 temp1 = 2*i*func(i-1,j-1);

	uint32 temp2 = 0;
	if (i >= 3)
	{
		for (uint16 k=1; k<=(i-2); k++)
		{
			temp2 += i*binomial_coefficient(i-2, k)*func(i-1-k,j-1)*func(k,j-1);
		}
	}

	return (temp1 + temp2);
}

int main(void)
{
	uint16 cnt = 0;
	
	cin>>cnt;

    for(uint16 k=1; k<=cnt; k++)
    {
        uint16 i = 0;
		uint16 j = 0;
		cin>>i>>j;

        cout << "Case #"<<i<<": " <<(func(i,j) - func(i,j-1))<<endl;
    }
		
	return 0;
}