跳转至

例题：整数划分⚓︎

代码1；代码2

描述⚓︎

一个正整数 \(n\) 可以表示成若干个正整数之和，形如：

\[ n=n_1+n_2+\cdots +n_k\,\,\left( n_1\geqslant n_2\geqslant \cdots \geqslant n_k, k\geqslant 1 \right) \]

我们将这样的一种表示称为正整数 \(n\) 的一种划分。

现在给定一个正整数 \(n\)，请求出 \(n\) 共有多少种不同的划分方法。

输入格式⚓︎

共一行，包含一个整数 \(n\)。

输出格式⚓︎

共一行，包含一个整数，表示总划分数量。

由于答案可能很大，输出结果请对 \(10^9 +7\) 取模。

数据范围⚓︎

\(1\leqslant n\leqslant 100\)

输入样例⚓︎

5

输出样例⚓︎

7

解答⚓︎

方法一⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010, mod = 1e9+7;

int n;
int f[N];

int main() {
    cin >> n;

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            f[j] = (f[j] + f[j - i]) % mod;
        }
    }
    cout << f[n] << endl;
    return 0;
}

方法二⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010, mod = 1e9+7;

int n;
int f[N][N];

int main() {
    cin >> n;

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    cout << res << endl;
    return 0;
}