传送门：点击打开链接
题目大意：正整数的划分数的数量
DP代码：（注：参考题解：点击打开链接）
/* 状态：dp[i][j]:把i分成最大不超过j的整数和的分法数量 转移方程：当j>i时, dp[i][j]=dp[i][i]; 当j==i时,dp[i][j]=1+dp[i][j-1]; 当j<i时, dp[i][j]=dp[i-j][j]+dp[i][j-1]; dp[i-j][j]:包括自己本身，相当于在含j的划分中，把要划分的数变小,查找 dp[i][j-1]:这一层的划分不含j，相当于把最大数的规模减小一层 例如： 5 当j>5时，由于最大的数只有5，所以dp[i][j]=dp[i][i] 当j==5时,只有一种+规模减小的dp 当j<5时，当j==4,5=4+1 当j==3,5=3+2 5=3+1+1 当j==2,5=2+2+1 5=2+1+1+1 当j==1,5=1+1+1+1+1 边界问题要注意一下：当要划分的数为1或者划分最大不能超过1时种数为1 */ #include<iostream> using namespace std; int main() { freopen("e:\\output.txt","w",stdout); int dp[121][121],i,j; for(i=1;i<=120;i++) dp[1][i]=dp[i][1]=1; for(i=2;i<=120;i++) for(j=2;j<=120;j++) { if(i<j) dp[i][j]=dp[i][i]; else if(i==j) dp[i][j]=dp[i][j-1]+1; else dp[i][j]=dp[i-j][j]+dp[i][j-1]; } while(cin>>i) cout<<dp[i][i]<<endl; return 0; }母函数模板AC代码：
#include<iostream> #define Maxnum 120 using namespace std; int main() { int i,j,k,c1[Maxnum+1],c2[Maxnum+1]; //初始化 for(i=0;i<=Maxnum;i++) { c1[i]=1; c2[i]=0; } //执行 for(i=2;i<=Maxnum;i++) { for(j=0;j<=Maxnum;j++) for(k=j;k<=Maxnum;k+=i) c2[k]+=c1[j]; for(j=0;j<=Maxnum;j++) { c1[j]=c2[j]; c2[j]=0; } } while(cin>>i) cout<<c1[i]<<endl; return 0; }母函数的话目前的理解就是把整数分解的问题看成是n个多项式相乘，指数代表合成的数，而该项的系数代表合成这个数的分法数量，这个可以表示成一个模板。多多益善吧，熟能生巧
