思路1
完全背包解法
容量为n,每个数的体积为1,2,3,4,…n
状态表示:
集合:$f[i][j]$表示只从1~i中选,且总和等于j的方案数
属性:cnt
状态转移方程:
集合的划分:和完全背包类似,以最后一步,即选$ai$,0个,1个,…,s个(s * i <= j)
$f[i][j] = f[i - 1][j] + f[i][j - i];$
状态转移的推论:
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i]+..+f[i-1][j-i*s]
f[i][j-i]= f[i - 1][j - i] + f[i - 1][j - 2 * i]+..+f[i-1][j-i*s]
即可得出:f[i][j] = f[i - 1][j] + f[i][j - 1];
闫式DP
代码
#include<iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int main(){
int n;
cin >> n;
//1个数都不选,总和为0,也是一种合法方案
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;
}
思路2
闫式DP
(与鸣人的影分身极其类似,我没打卡hh)
举个例子:
f[10][3],
即总和是10,个数是3,分成2部分
有1情况有:1 1 8, 1 2 7, 1 3 6, 1 4 5 ..
无1情况有: 2 2 6, 2 3 5, 2 4 4...
1.有1的情况:
直接将f[9][2]值拿过来,即 1 8 , 2 7, 3, 6, 4 5...(因为它们再加一个数1,则对应f[10][3]有1的情况)
2.没有1的情况:
相当于f[7][3]所有的组合加一,f[7][3]的所有情况等于f[10][3]无1的情况
例如f[7][3]: 1 1 5,1 2 4, 2 2 3, ...
当它们所有数加一后:
得到 2 2 6, 2 3 5, 3 3 4... 就是(对应了f[10][3]无1的情况)
所以f[i][j] = f[i - 1][j - 1] + f[i - j][j];
最后将所有的组合数加起来:ans = f[n][1] + f[n][2] + ... + f[n][n]
代码
#include<iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int n;
int main(){
cin >> 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; //注意res += f[n][i] % mod 这样写是错误的
cout << res << endl;
return 0;
}