例题 Acwing900 整数划分

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

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

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

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

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

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

数据范围
1≤n≤1000

输入样例:
5
输出样例：
7

解法一：

看成完全背包问题

f[i,j]: 只从前i个数中选，数的和恰好为j的所有集合的数量
状态划分

f[i,j] = f[i-1,j] + f[i-1,j-i] + f[i-1][j-2i] +…… f[i-1][j-si] //si<=j 且为最大s
//优化：
f[i,j-i]= f[i-1][j-i]+ f[i-1][j-2i] +…… f[i-1][j-si] //和多重背包的区别是此处最多s受体积限制，多重背包受数量限制
//结果：
f[i,j] = f[i-1][j] + f[i][j-i];
//减维
f[j] = f[j] + f[j-i] //完全背包j循环正序

代码

const N = 1010;
let f = new Int32Array(N);

let mod = 1e9 + 7;
let n = 0;

let buf = '';
process.stdin.on('readable', function () {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            f[0] = 1;   //和为0只有1种
            for (let i = 1; i <= n; i++) {
                for (let j = i; j <= n; j++) {
                    f[j] = (f[j] + f[j - i]) % mod
                }
            }
            console.log(f[n]);
        }
    });
});

解法二

f[i,j] : 只从前i个数中选，数的和恰好为j的所有集合的数量
状态划分：

最后一位选1的 所有选法最后一位1去掉，选法数量不变f[i,j] = f[i-1][j-1]
最后一位没选1的 所有选法每一个数减1，选法数量不变 f[i,j] = f[i][j-i]
f[i,j] = f[i-1][j-1] + f[i][j-i]

f[1,n]+f[2,n]+f[3,n]+……+f[n,n] //结果
代码

const N = 1010;
let f = [];
for (let i = 0; i < N; i++) f[i] = new Int32Array(N);

let mod = 1e9 + 7;
let n = 0;

let buf = '';
process.stdin.on('readable', function () {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            f[0][0] = 1;   //选0个数，和为0
            for (let j = 1; j <= n; j++) {   //j为和
                for (let i = 1; i <= j; i++) {   //i为只从前i个数中选
                    f[i][j] = (f[i - 1][j - 1] + f[i][j - i]) % mod;
                }
            }
            let res = 0;
            for (let i = 1; i <= n; i++) res = (res + f[i][n]) % mod;
            console.log(res);
        }
    });
});