递归非递归整数划分c➕➕代码

整数划分是将一个正整数拆分成若干个正整数之和的方式，不考虑顺序和个数。例如，对于整数4，它的整数划分有5种：4、3+1、2+2、2+1+1、1+1+1+1。递归和非递归都可以实现整数划分，下面分别介绍。

递归实现整数划分的代码如下：

#include <iostream>
using namespace std;

int partition(int n, int m) {
    if (n == 1 || m == 1) {
        return 1;
    }
    if (n < m) {
        return partition(n, n);
    }
    if (n == m) {
        return partition(n, m - 1) + 1;
    }
    return partition(n, m - 1) + partition(n - m, m);
}

int main() {
    int n;
    cin >> n;
    cout << partition(n, n) << endl;
    return 0;
}

非递归实现整数划分的代码如下：

#include <iostream>
using namespace std;

int partition(int n) {
    int dp[n + 1] = {0};
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            dp[j] += dp[j - i];
        }
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << partition(n) << endl;
    return 0;
}