题目描述
一个正整数n可以表示成若干个正整数之和,形如:n=n1+n2+…+nk,其中n1≥n2≥…≥nk,k≥1。
我们将这样的一种表示称为正整数n的一种划分。
现在给定一个正整数n,请你求出n共有多少种不同的划分方法。
输入格式
共一行,包含一个整数n。
输出格式
共一行,包含一个整数,表示总划分数量。
由于答案可能很大,输出结果请对109+7取模。
数据范围
1≤n≤1000
输入样例:
5
输出样例:
7
思路1 完全背包思想
思路:把1,2,3, … n分别看做n个物体的体积,这n个物体均无使用次数限制,问恰好能装满总体积为n的背包的总方案数(完全背包问题变形)
初值问题:
完全背包问题中求最大值时,
当都不选时,价值显然是 0
即:for (int i = 0; i <= n; i ++) f[i][0] = 0;
等价变形后: f[0] = 0
计数类问题求方案数时,
当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1
即:for (int i = 0; i <= n; i ++) f[i][0] = 1;
等价变形后: f[0] = 1
状态计算 + 优化思路:
f[i][j] 表示前i个整数(1,2…,i)恰好拼成j的方案数
求方案数:把集合选0个i,1个i,2个i,…全部加起来
f[i][j] = f[i - 1][j] + **f[i - 1][j - i] + f[i - 1][j - 2 * i] + ... + f[i - 1][j - s * i];**
f[i][j - i] = **f[i - 1][j - i] + f[i - 1][j - 2 * i] + ... + f[i - 1][j - s * i];**
f[i][j] = f[i − 1][j] + f[i][j − i];
有兴趣可以先看一下完全背包的题解,比较两者的区别 https://www.acwing.com/solution/content/34360/
c++ 初始代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 7, mod = 1e9 + 7;
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 0; i <= n; i ++) {
f[i][0] = 1; //一个都不选的情况下,组合为0, //背包问题的理解 容量为0时,前 i 个物品全不选也是一种方案
}
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= n; j ++) {
f[i][j] = f[i - 1][j] % mod; // 特殊 f[0][0] = 1
if (j >= i) f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
}
}
cout << f[n][n] << endl;
}
c++
#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; //一个都不选的情况下,组合为0, //背包问题的理解 容量为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;
}
思路2
如图所示,集合的划分按照由j个正整数构成和为i,
那么构成划分成两个区域:
1.最小值为1的构成 f[i, j] = 1 + f[i - 1, j -1],我们只需要直到f[i - 1, j - 1]的方案数即可
2.最小值不为1的构成 f[i, j] = f[i - j, j] 将总和i - j * 1, 再有j个数构成i,则j个数的值一定大于整数1
由此可以得到
f[i, j] = f[i - 1, j - 1] + f[i - j, j]
f[i, j] 由j个正整数构成和为i,
结果ans = f[i, 1] + f[i, 2] + f[i, 3] + ...+f[i, i];
#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; //组合为0的情况下,用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;
}