整数分解方法——腾讯2017春招真题

如下示例：

1：共0种分解方法；

2：共0种分解方法；

3：3=2+1 共1种分解方法；

4：4=3+1=2+1+1 共2种分解方法；

5：5=4+1=3+2=3+1+1=2+2+1=2+1+1+1 共5种分解方法

6：6=5+1=4+2=4+1+1=3+2+1=3+1+1+1=2+2+1+1=2+1+1+1+1 共7种分解方法

以此类推，求一任意整数num有几种分解方法？

思路：

• 对于数num，按照分解情况的结尾数字考虑：以1结尾，以2结尾，...，以floor((num - 1) / 2)结尾，每种结尾都先进行一次分解(以7为例，以1结尾时分解成6+1，以2结尾分解成5+2，以3结尾分解成4+3)
• 对于第一次分解出的两个数(num1，num2)，进一步分解num1，且只在num1 > 2*num2 时分解num1(否则无法保证降序，例：5=3+2，3继续分解出2+1，则5=2+1+2不是降序)
• 若num1是偶数，计算分解情况时+1(例：5=4+1，进一步分解4时，要考虑4=2+2)
• 保证num1进一步分解的结尾的数>=num2(例：7=5+2，进一步分解5时，只能将5分解成3+2，若分解成任意以1结尾的情况，如4+1，则7=4+1+2不是降序)
• 因此，我们运用动态规划的方法，从3开始往大数分析，构造二维数组arr[i][j]，arr[i][j]表示分解结尾数为j+1(下标从0开始)时的分解种数，即将第i+1行所有列相加即为num=i+1时的分解方法总数

C++   AC code：

 1 #include <iostream>
 2 #include <vector>
 3 #include <cmath>
 4 
 5 using namespace std;
 6 
 7 int main() {
 8     int num;
 9     while (cin >> num) {
10         int result = 0;
11 
12         vector<vector<int>> arr(num + 1, vector<int>());//二维容器，第一维长度num+1，第二维长度不定
13 
14         for (int i = 3; i <= num; i++) {
15             int columnNum = (i - 1) / 2;//隐式转换
16 
17             arr[i].resize(columnNum);//定义arr[i][]第二维长度
18 
19             for (int j = 0; j < columnNum; j++) {
20                 arr[i][j] = 1;//arr[i][]数据初始化，对应思路1.
21 
22                 int num2 = j + 1;
23                 int num1 = i - num2;
24 
25                 if (num1 > 2 * num2) { //对应思路2. 只有在这种情况下才进行分解
26                     if (num1 % 2 == 0) { //对应思路3. 如果num1是偶数，则增加计数
27                         arr[i][j]++;
28                     }
29 
30                     // 计算num1的分解，对应思路4. k范围是[num2,columnNum)
31                     for (int k = j; k < arr[num1].size(); k++) {
32                         arr[i][j] += arr[num1][k];//不能从k=0开始加，否则无法保证分解结果降序，即种数计算有重复
33                     }
34                 }
35             }
36         }
37 
38         if (num == 1 || num == 2) {
39             result = 0;
40         } else {
41             for (int i = 0; i < arr[num].size(); i++) {
42                 result += arr[num][i];
43             }
44         }
45 
46         cout << result << endl; // 使用C++的cout进行输出
47     }
48 
49     return 0;
50 }