首页 > 代码库 > hdu1028：整数拆分
hdu1028：整数拆分
求整数的拆分数。。
一种解法是母函数
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int dp[2][130];int main(){ int n; while(scanf("%d",&n)!=EOF) { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=n;j++) { for(int k=0;j+k*i<=n;k++) { dp[i%2][j+k*i]+=dp[(i-1)%2][j]; } dp[(i-1)%2][j]=0; } } printf("%d\n",dp[n%2][n]); } return 0;}
还有一种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 10000int dp[130][130];int dfs(int n,int m){ if(dp[n][m]!=-1) return dp[n][m]; if(m==0) return dp[n][0]=0; if(n==0) return dp[0][m]=1; if(m>n) return dfs(n,n); return dp[n][m]=dfs(n,m-1)+dfs(n-m,m);}int main(){ memset(dp,-1,sizeof(dp)); int t,x; while(scanf("%d",&x)!=EOF) { printf("%d\n",dfs(x,x)); } return 0;}
hdu1028：整数拆分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。