整数划分问题【递归以及递推求解方式】

Myth丶恋晨 2022-05-12 06:42 208阅读 0赞

## 简述 ##

**用一系列正整数之和来表示一个整数，称之为整数划分。而整数划分问题则对于某个数字，输出对应整数划分的数量。**  
先写递归，有了递归之后，就换用递推来加快速度。

## 算法思路 ##

*  `q(n, m)`表示，n这个整数被划分，其中最大可能整数是m的所有划分情况数目。**明显，所求，即为`q(n,n)`**
 *  当`m>n`时，明显有 `q(n, m) = q(n, n)`。因为，保证了所有整数都必须是大于等于1的。所以，限制再高的上限都没有任何的意义。
 *  当`m=n`时候，明显有两种划分，第一种就是**全部拿走**，另一种就是**不全部拿走，那最大可能即为n-1**。即，`q(n,n) = 1+q(n, n-1)`。
 *  当`m<n`时候，同之前的方法类似。要么是不拿走当前最大值的可能，要么就是拿走最大值的。即，`q(n, m) = q(n, m-1) + q(n-m, m)`

为什么需要考虑后面的两种分开，主要是为了避免`n==0 (n-m == 0)`的时候需要求解。

## 递归 ##

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

## 递推求解 ##

#include <iostream>
    using namespace std;
    
    
    unsigned int** arr;
    
    void cal(int n){ 
    	arr = new unsigned*[n+1];
    	for (int i = 0; i <= n; ++i) arr[i] = new unsigned[n+1];
    
    	for (int i = 1; i <= n; ++i) arr[i][1] = 1; // max number equal to 1
    	// arr[i][j] 表示i这个数被划分时，最大可能的数为j的所有可能。
    	for (int i = 1; i <= n; ++i)
    		for (int j = 2; j <= n; ++j)
    			if (i < j) arr[i][j] = arr[i][i];
    			else if (i == j) arr[i][j] = 1 + arr[i][j-1];
    			else arr[i][j] = arr[i][j-1] + arr[i-j][j]; 
    
    	cout << arr[n][n]<< endl;
    
    	for (int i = 0; i <= n; ++i) delete []arr[i];
    	delete [] arr;
    }
    
    int main(){ 
    	int n;
    	while(cin >> n && n >= 1)
    		cal(n);
    }

## 递归方式以及路径输出 ##

#include <iostream>
    using namespace std;
    #include <string>
    
    void cal(int n, int m, string s){ 
        if (n == 0 || m == 0) return;
        if (n==1||m==1) { 
            for (int i = 0; i < n-1; ++i) s += string("1+");
            cout << s<< "1\n";
            return;
        }
        if (m > n){ 
            return cal(n, n, s);    
        } 
        if (n==m) { 
            cout << s<< n<< endl;
            return cal(n, m-1, s);
        }
        if (n-m != 0)
            cal(n-m, m, s + to_string(m) + string("+"));
        else { 
            cout << s<< m<< endl;
        }
        cal(n, m-1, s);
    }
    
    int main(){ 
        int n;
        string s;
        while(cin >> n && n >= 1)
            cal(n, n, s);
    }