非背包解法
f[i][j] 代表总和为i, 由j个数组成的所有方案数.
集合划分为2部分, 第一部分的最小值为1, 减去这个1, 为f[i-1][j-1],
第二部分的最小值大于1, 给所有数都减去1, 为 f[i-j][j].
初始化 f[1][1]=1, i从2开始遍历即可; 或者将f[i][1]都设置为1, 从1开始遍历也可以.
f[i][1]为什么等于1呢? 和为i且只用了一个数, 那只有用i自己才行, 只有这一种方案.
#include <iostream>
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];
if (i >= j)
f[i][j] = (f[i][j] + 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;
}
完全背包解法
二维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int ans;
int main() {
cin >> n;
//f[0] = 1;
for (int i = 1; i <= n; i++) f[i][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= i) f[i][j] = (f[i][j] + f[i][j - i]) % mod;
}
cout << f[n][n] << endl;
return 0;
}
一维
#include <iostream>
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;
}