整数划分问题详解：一个递归算法的诞生与优化

整数划分问题详解：一个递归算法的诞生与优化

整数划分问题是组合数学中的一个经典问题，具有广泛的应用场景，如计算机科学、密码学等。本文将深入探讨整数划分问题的递归求解方法，并给出具体的代码实现。

问题定义与记号引入

我们首先引入记号q(n,m)，表示在正整数n的所有不同划分中，最大加数n1不大于m(即n1≤m)的划分个数。本题要求的p(n)，实际上就是q(n,n)。

递推式的推导

分析整数6的11种不同划分的构成，可以得到一个最重要的递推式子：当1<m<n时，q(n,m)=q(n-m,m)+q(n,m-1)。如下图所示。

当n=6,m=3时，有：q(6,3)=q(6-3,3)+q(6,2)，q(6,3)表示最大加数不超过3的划分数，即虚线以下3行包括的划分，其中第一行是3开头的划分，个数是q(6-3,3)，即从6中扣除3，剩下的值(即3)的最大加数不超过3的划分，后两行是q(6,2),表示最大加数不超过2的划分数

再补充一些边界情形，就可以建立q(n,m)的递归关系(n,m均为≥1的整数)：

1. 当n=1或m=1时，q(n,m)=1

• 当最大加数n1不大于m=1时，任何正整数n只有一种划分形式，即n=1+1+…+1
• 而当n=1时，也只有一种划分形式，即n=1

2. 当m>n时，q(n,m)=q(n,n)

• 最大加数n1实际上不能大于n，因此当m>n时，q(n,m)=q(n,n)

3. 当n=m时，q(n,m)=q(n,n)=1+q(n,n-1)

• 正整数n的划分由n1=n的划分(只有1种划分，就是n本身)和n1≤n-1的划分组成。

4. 当n>m>1时，q(n,m)=q(n,m-1)+q(n-m,m)

• 正整数n的最大加数n1不大于m的划分(个数为q(n,m),由n1=m的划分（个数为q(n-m,m)和n1≤m-1的划分(个数为q(n,m-1)组成

因此，可以得到下式所示的递推关系。这个递推式子很容易转换成一个递归函数，从而本题可以用递归方法求解。

初始递归代码实现

#include<iostream>
using namespace std;
long long q(int n, int m){
    if(n<1 || m<1) return 0;
    else if(n==1 || m==1) return 1;
    else if(m>n) return q(n, n);
    else if(n==m) return (q(n, n-1)+1);
    else return (q(n, m-1)+q(n-m, m));
}
int main()
{
    int n; 
    while(cin >> n)
        cout << q(n,n) << endl;
    return 0;
}  

代码优化

由于初始递归代码在大数据时会运行超时，因此需要进行优化。引入二维数组record，record[n][m]记录求得的q(n,m)。

#include<iostream>
using namespace std;
long long record[401][401]; //全局变量，编译器将各元素值初始化为0
long long q(int n, int m){
    if(record[n][m]) return record[n][m];
    if(n<1 || m<1) return record[n][m]=0;
    else if(n==1 || m==1) return record[n][m]=1;
    else if(m>n) return record[n][m]=q(n, n);
    else if(n==m) return record[n][m]=(q(n, n-1)+1);
    else return record[n][m]=(q(n, m-1)+q(n-m, m));
}
int main()
{
    int i, j, n;
    for(i=1;i<=400;i++){ //求出所有的q(n,m)
        for(j=1;j<=i;j++) record[i][j] = q(i,j);
}
    while(cin >> n)
        cout << q(n,n) << endl;
    return 0;
}  

在优化后的代码中：

1. 定义了一个二维数组record，record[n][m]记录求得的q(n,m)
2. 在递归函数q里，增加了一条语句：当record[n][m]的值非0，意味着已经求出了record[n][m]，则不递归求解，而是直接返回其值
3. 每个条件分支里都是先对record[n][m]赋值，再返回record[n][m]的值
4. 在main函数里，用一个二重循环求出所有的q(n,m)，m≤n≤400，即只求出二维数组record主对角线及以下元素的值
5. 最后，对输入的每个n值，答案p(n)=q(n,n)=record[n][n]直接输出即可

下图给出了求得的record数组部分元素的值，根据这些值，也可以验证上述递推式子。需要说明的是，在record数组里，包含了整数1~400的划分数（对角线上的值）。