给定一个整数n，要找出n能拆分成多少种不同的若干个数的和与乘积的形式。比如：
4=4 12=1*12
4=1+3 12=2*6
4=2+2 12=3*4
4=1+1+2 12=2*2*3
4=1+1+1+1
先看加法形式，可以构造一个母函数F(x)=(1+x+x^2+...+x^n)(1+x^2+x^4+...+x^n)...(1+x^n)，将这个母函数展开后，求出每一个x^k前面的系数Ck，就是对应的整数K有多少种拆分的形式。
1 #include <iostream>
2 using namespace std;
3
4 const int MAXN = 120;
5 int c1[MAXN+1],c2[MAXN+1];
6
7 int main(){
8 int i,j,k,n;
9 for(i=0;i<=MAXN;i++)
10 c1[i]=1,c2[i]=0;
11 for(i=2;i<=MAXN;i++){
12 for(j=0;j<=MAXN;j++)
13 for(k=0;k+j<=MAXN;k+=i)
14 c2[j+k]+=c1[j];
15 for(j=0;j<=MAXN;j++)
16 c1[j]=c2[j],c2[j]=0;
17 }
18 while(cin>>n) cout<<c1[n]<<endl;
19 return 0;
20 }
对于乘积的形式，设n=i*j，dp[n]为整数n拆分成乘积形式的个数，dp[n]=∑dp[i]=∑dp[j] (i∈{i : i*j=n}，j∈{j : i*j=n})，这就是这个问题的状态转移方程，具有动态规划问题的最有子结构性质。
1 #include <iostream>
2 using namespace std;
3
4 const int MAXN = 200000;
5 int dp[MAXN+1];
6
7 int main(){
8 int i,j,n;
9 for(dp[1]=1,i=2;i<=MAXN;i++)
10 for(j=1;i*j<=MAXN;j++)
11 dp[i*j]+=dp[j];
12 while(cin>>n) cout<<dp[n]<<endl;
13 return 0;
14 }