算法 - 整数划分

---

来源： https://www.acwing.com/problem/content/902/

描述：

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

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

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

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

---

方法一、 完全背包

可以类似于完全背包问题进行处理，可以变成物品i = 0 ~ n， j = n；这样进行处理。

dp分析

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

• 集合： f[i][j] 表示，选i个物品，恰好背包装满容量为j。
• 属性： Count

状态计算

• 第i件可以选择0， 1， 2， 3， 4 …， s件，恰好装满
• 所以就等于集合的相加。
• 状态转移方程就可以写为： $f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i]…f[i - 1][j - si]$

状态转移方程优化：

f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i]....f[i - 1][j - si]
f[i][j - i] =           f[i - 1][j - i] + f[i - 1][j - 2i]....f[i - 1][j - si]

所以，状态转移方程就可以写为 $f[i][j] = f[i - 1][j] + f[i][j - i]$

同样可以优化为1维度。这里只需要从小到大进行循环就行。 $f[j] = f[j] + f[j - i]$

#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;
}

方法二、计数DP分析

计数dp分析：

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

• 集合： 表示累加和为i，累加和的长度为j的数
• 属性： Count

状态计算：

• 分解为长度等于1和长度大于1两个部分
• 如果长度等于1，f[i][j] = f[i - 1][j - 1]，f[i - 1][j - 1]长度为1
• 如果长度大于1，f[i][j] = f[i - j][j] 表示i - j的数的长度为j的值
• 所以某个数的长度就是： f[n][1] + f[n][2] … f[n][n]

所以状态转移方程： $f[i][j] = f[i - 1][j - 1] + f[i - j][j]$

C++实现：

#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[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;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;

    cout << res << endl;
    return 0;
}