题意是求所给的数能够被拆分成的不同组合数目。
方法有三种：
一、完全背包。
限制条件：所用数字不大于 n。
目标：求分解种数（组合出 n 的方法数)。
令 dp[ i ][ j ] = x 表示 用前 i 种数字组合出数字 j 有 x 种方法。
状态转移方程：dp[ i ][ j ] = dp[ i -1 ][ j ] + dp[ i ][ j - num[i] ]
方程解释：前 i 种数字组合出数字 j 的方法数 = 前 i - 1 种数字组合出数字 j 的方法数（不用第 i 种数字）+ 至少用一次第 i 种数字的方法数。
用滚动数组求解，代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int dp[122]; 4 void init() 5 { 6 dp[0] = 1; 7 for(int i = 1; i <= 122; ++i) 8 for(int j = i; j <= 122; ++j) 9 dp[j] += dp[j-i]; 10 } 11 int main() 12 { 13 int n; 14 init(); 15 while(~scanf("%d",&n)) 16 printf("%d ",dp[n]); 17 return 0; 18 }
二、分治。
令 sol(a, b) 表示 a 被最大数字为 b 的数字分解成的种数。则
当 a == 1 && b == 1 时，只能分解成 1 种；
当 a < 1 || b < 1 时，一种也没有，即只能分解成 0 种；
当 a == b 时，则 分解种数 = 含 b 的数字分解种数（仅 1 种） + 不含 b 的数字分解种数，即 sol(a, b) = 1 + sol(a, b - 1)；
当 a < b 时，则 分解种数 = 最大数字为 a 的分解种数，即 sol(a, b) = sol(a, a)；
当 a > b 时，则 分解种数 = 没有 b 的数字分解种数 + 至少含有 1 个 b 的数字分解种数，即 sol(a, b) = sol(a, b-1) + sol(a-b, b)。
打表求解，代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int a[121]={0,1,2,3,5,7,11,15,22, 4 30,42,56,77,101,135,176,231,297,385,490, 5 627,792,1002,1255,1575,1958,2436,3010,3718, 6 4565,5604,6842,8349,10143,12310,14883,17977, 7 21637,26015,31185,37338,44583,53174,63261, 8 75175,89134,105558,124754,147273,173525,204226, 9 239943,281589,329931,386155,451276,526823,614154, 10 715220,831820,966467,1121505,1300156,1505499, 11 1741630,2012558,2323520,2679689,3087735,3554345, 12 4087968,4697205,5392783,6185689,7089500,8118264, 13 9289091,10619863,12132164,13848650,15796476,18004327, 14 20506255,23338469,26543660,30167357,34262962,38887673, 15 44108109,49995925,56634173,64112359,72533807,82010177, 16 92669720,104651419,118114304,133230930,150198136, 17 169229875,190569292,214481126,241265379,271248950, 18 304801365,342325709,384276336,431149389,483502844, 19 541946240,607163746,679903203,761002156,851376628, 20 952050665,1064144451,1188908248,1327710076,1482074143, 21 1653668665,1844349560}; 22 //数组的求解方法 23 //int sol(int a,int b) 24 //{ 25 // if(a==1||b==1) return 1; 26 // else if(a<1||b<1) return 0; 27 // else if(a==b) return sol(a,b-1)+1; 28 // else if(a>b) return sol(a,b-1)+sol(a-b,b); 29 // else if(a<b) return sol(a,a); 30 //} 31 int main() 32 { 33 int n; 34 while(~scanf("%d",&n)) 35 printf("%d ",a[n]); 36 return 0; 37 }
三、母函数。