求整数的拆分数。。
一种解法是母函数
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
int dp[][];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
for(int k=;j+k*i<=n;k++)
{
dp[i%][j+k*i]+=dp[(i-)%][j];
}
dp[(i-)%][j]=;
}
}
printf("%d\n",dp[n%][n]);
}
return ;
}
还有一种dp的方法
dp[n][m]表示 把n拆分成不大于 m的数的方案数
转移的时候按照拆分中的最大的数分类一下。。
dp[n][m]=sum {i=1~n} ( dp[i][n-i] )----分类中最大数为 1~n
代码写成递归的记忆化搜索了
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define MAXN 10000
int dp[][];
int dfs(int n,int m)
{
if(dp[n][m]!=-)
return dp[n][m];
if(m==)
return dp[n][]=;
if(n==)
return dp[][m]=;
if(m>n)
return dfs(n,n);
return dp[n][m]=dfs(n,m-)+dfs(n-m,m);
}
int main()
{
memset(dp,-,sizeof(dp));
int t,x;
while(scanf("%d",&x)!=EOF)
{
printf("%d\n",dfs(x,x));
} return ;
}