进阶递归之简单的整数划分问题
时间: 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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。