题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1028
题意：
给你一个正整数n，将n拆分成若干个正整数之和，问你有多少种方案。
注："4 = 3 + 1"和"4 = 1 + 3"视为同一种方案。（加数是无序的）
题解1(dp)：
表示状态：
dp[n][m] = num of methods
表示用均不超过m的元素组成n的方法数。
如何转移：
假设当前状态为dp[n][m].
对于等于m的元素，有两种决策。要么不用，要么用。
（1）不用：dp[n][m] += dp[n][m-1]
（2）用： dp[n][m] += dp[n-m][m]
综上：dp[n][m] = dp[n][m-1] + dp[n-m][m]
找出答案：
ans = dp[n][n]
边界条件：
dp[0][i] = 1 (0<=i<=MAX_N)
题解2（母函数）：
要凑出n，每种方案无非是取几个1，几个2，几个3......
这就是母函数的经典问题啦（取硬币）。
构造母函数：
G(x) = (1 + x^1 + x^2 + x^3...) * (1 + x^2 + x^4 + x^6...) * (1 + x^3 + x^6 + x^9...) * (1 + x^4 + x^8 + x^12...)...
找出答案：
x^n项的系数即为答案。
AC Code(dp):
// dp[n][m] = num of methods
// n: the elems are up to n
// m: each elem won't be not more than m
// dp[n][m] = dp[n][m-1] + dp[n-m][m]
// ans = dp[n][n]
// dp[0][m] = 1 #include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 125 using namespace std; int n;
int dp[MAX_N][MAX_N]; void cal_dp()
{
memset(dp,,sizeof(dp));
for(int i=;i<MAX_N;i++)
{
dp[][i]=;
}
for(int i=;i<MAX_N;i++)
{
for(int j=;j<MAX_N;j++)
{
if(i>=j) dp[i][j]=dp[i][j-]+dp[i-j][j];
else dp[i][j]=dp[i][i];
}
}
} int main()
{
cal_dp();
while(cin>>n)
{
cout<<dp[n][n]<<endl;
}
}
AC Code(Generating Function):
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 125 using namespace std; int n;
int ans[MAX_N];
int temp[MAX_N]; void generating_function(int n)
{
memset(ans,,sizeof(ans));
ans[]=;
for(int i=;i<=n;i++)
{
memset(temp,,sizeof(temp));
for(int j=;j*i<=n;j++)
{
for(int k=;k+j*i<=n;k++)
{
temp[k+j*i]+=ans[k];
}
}
memcpy(ans,temp,sizeof(temp));
}
} int main()
{
generating_function();
while(cin>>n)
{
cout<<ans[n]<<endl;
}
}