給定一個整數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})，這就是這個問題的狀態(tài)轉移方程，具有動態(tài)規(guī)劃問題的最有子結構性質。
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 }