python/TangDou/AcWing/JiShuDP/900.md

##AcWing 900. 整数划分

一、题目描述

一个正整数 n 可以表示成若干个正整数之和，形如：n=n_1+n_2+…+n_k，其中 n_1≥n_2≥…≥n_k,k≥1。

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

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

输入格式 共一行，包含一个整数 n。

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

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

数据范围 1≤n≤1000

输入样例:

5

输出样例：

7

二、解题思路

把整数n看成一个容量为n的背包，有n种物品，物品的体积分别是1-n,我们要求的是 恰好 装满背包的方案数(计数)，每种物品 可以用无限次，所以可以看成是一个完全背包。

先考虑二维的状态描述方法：

f[i,j]：从前i中选，总和是j的选法,值就是方案数量。

• 第i个物品选择了0个 表达式：f[i-1,j] ，含义：在前i个物品中选择，结果现在第i个物品选择了0个，就是说这j个体积都是前i-1贡献的。

• 第i个物品选择了1个 表达式：f[i-1,j-1 * i] 含义：在前i个物品中选择，结果现在第i个物品选择了1个，就是说这 j-1*i 个体积都是前i-1贡献的。

• 第i个物品选择了2个 f[i-1,j-2*i]

...

• 第i个物品选择了s个 f[i-1,j-s*i]

初值问题

求最大值时，当都不选时，价值显然是 0。

求方案数时，当都不选时，方案数是 1

即：

for (int i = 0; i <= n; i ++) f[i][0] = 1;

二、二维代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int MOD = 1e9 + 7;
int n;
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) f[i][0] = 1;

    for (int i = 1; i <= n; i++)       // 枚举每个物品，物品的序号与物品的体积是相等的，都是i
        for (int j = 1; j <= n; j++) { // 枚举背包容量j
            if (j >= i)                // ① 背包容量j>=当前体积i,可以选择当前数字
                f[i][j] = (f[i][j - i] + f[i - 1][j]) % MOD;
            else
                f[i][j] = f[i - 1][j] % MOD; // ② 放弃当前数字
        }

    cout << f[n][n] << endl;
    return 0;
}

三、一维代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const int MOD = 1e9 + 7;
int f[N];
int n;

int main() {
    cin >> n;
    f[0] = 1; // 容量为0时，前 i 个物品全不选也是一种方案
    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;
}