完全背包问题
f[i][j]
表示所有从 前 i 个数中选,总和为 j 的所有方案
状态转移方程
f[i][j] = f[i-1][j] + f[i][j - 1]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
/*
完全背包 : 把 1 2 3 ... n 分别看做 n 个物体的体积 n 个物体均无使用限制
f[i][j] 表示 前 i 个数 1 2 3 .. i 恰好拼凑成 j 的方案的总数
从第 i 个数选几个进行划分 保证 s*i <= j
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];
*/
int main(){
scanf("%d", &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;
printf("%d\n", f[n]);
return 0;
}
其他方法
状态表示
f[i][j]
表示 总和是 i, 恰好表示成 j 个数的方案
状态转移方程
f[i][j] = f[i-1][j-1] + f[i-j][j]
把集合划分成 组成 i 的数最小是 1 和 最小的数大于等于 1
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main(){
scanf("%d", &n);
f[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;
printf("%d\n", res);
return 0;
}