正整数划分.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 43 行

#include<stdio.h>
#include<stdlib.h>
int dp[2000][2000];

main()
{
	int n;
	int kind(int ,int );
	scanf("%d",&n);
	int sum=kind(n,n);
	printf("%d",sum);
	return 0;
}
int kind(int n,int m)
{
	if(dp[n][m])
	{
		return dp[n][m];
	}
	if(m==1)
	{
		dp[n][m]=1;
		return dp[n][m];
	}
	if(n==1)
	{
		dp[n][m]=1;
		return dp[n][m];
	}
	if(m>n)
	{
		dp[n][m]=kind(n,n);
		return dp[n][m];
	}
	if(m==n)
	{
		dp[n][m]=1+kind(n,m-1);
		return dp[n][m];
	}
	dp[n][m]=kind(n,m-1)+kind(n-m,m);
	return dp[n][m];

}