题目描述

一个正整数n可以表示成若干个正整数之和，形如：$n = n_1 + n_2 +…+n_k$，其中$n_1 \geq n_2 \geq … \geq n_k , k \geq 1。$
我们将这样的一种表示称为正整数n的一种划分。

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

输入格式

共一行，包含一个整数n。

输出格式

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

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

数据范围

$1 \leq n \leq 1000$

样例

输入样例:

5

输出样例：

7

看做完全背包

1-n这n个数中，每个数有无限多个，求构成n的方案数

状态表示f[i][j]

集合：从1~i中挑选数字，恰好构成j的组合

属性：方案数量

状态计算：

f[i][j] = f[i - 1][j] + f[i][j - i]

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int n;

int main() {
    cin >> n;

    for(int i = 0; i <= n; i ++ ) f[i][0] = 1;//容量为0时，什么都不选也是一种方案

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

    cout << f[n][n] << '\n';

    return 0;
}

优化为一维（同完全背包，j从小到大循环）

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int 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] << '\n';
    return 0;
}

另一种dp想法

状态表示`f[i][j]``

集合：i由j个数所组成

属性：方案数量

状态计算

j个数里最小值为1时，删除一个1，即有f[i - 1][j - 1]种。

j个数里最小值大于1时，所有数删除一个1，即有f[i - j][j]种。

f[i][j] = f[i - 1][j - 1] + f[i - j][j];

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int n;

int main() {
    cin >> n;
    f[1][1] = 1;//方案数

    for(int i = 2; 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 << '\n';

    return 0;
}