poj 3014 Cake Pieces and Plates 整數拆分

poj 3014 Cake Pieces and Plates 整數拆分

題意：

將m拆成n個數，允許某個數為0，求拆分方案數。

分析：

裸的整數拆分，設h(m,n)表示將m拆成n個數，允許某數為0的方案數，遞推方程見代碼。很有意思的是，參考上一篇寫poj1221的博文中，設f(m,n)表示將m進行任意份數不允許有0的整數拆分，且最大元素小於等於m的方案數，則h(m,n)==f(m,n)。。。。求解此等式意義。。。

代碼：

//poj 3014
//sep9
#include 
using namespace std;
const int maxN=4500;
const int mod=1000000007;

int a[maxN+10][maxN+10];
int main()
{
	int m,n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j){
			if(i==1||j==1)
				a[i][j]=1;
			else if(j>i)
				a[i][j]=a[i][i];	
			else if(j==i)
				a[i][j]=a[i][j-1]+1;
			else{
				a[i][j]=(a[i][j-1]+a[i-j][j]);
				if(a[i][j]>=mod)
					a[i][j]-=mod;
			}
		}
	printf("%d\n",a[m][n]%mod);
	return 0;	
}