进阶递归之简单的整数划分问题

进阶递归之简单的整数划分问题

时间： 1ms        内存：128M

描述：

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入：

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

输出：

对于每组测试数据，输出N的划分数。

示例输入：

5

示例输出：

7

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
int num=0,s;
void dfs(int n,int sum)
{
    int i;
    if(sum==s)
    {
        num++;
        return;
    }
    for(i=n;i>=1;i--)
    {
        if(sum+i<=s)
        dfs(i,sum+i);
    }
}
int main()
{
    while(scanf("%d",&s)!=EOF)
    {
        num=0;
        dfs(s,0);
    printf("%d\n",num);
    }
}

参考答案（时间最优[2]）：

#include<stdio.h>
int main()
{
	int n;
	int dp[51][51]={0};
	for(int i=1;i<=50;i++)
	{
		dp[0][i]=1;
	}
	for(int i=1;i<=50;i++)
	for(int j=1;j<=50;j++)
	{
		if(i<j)
		{
			dp[i][j]=dp[i][j-1];
		}
		else
		dp[i][j]=dp[i-j][j]+dp[i][j-1];
		}
		while(scanf("%d",&n)!=EOF)
	{
	printf("%d\n",dp[n][n]);
}
	return 0;
} 

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。