题目描述
blablabla
样例
blablabla
算法1
二维数组的写法
注意初始化, f[0][0] 什么都不选 就是 1, 当f[i][0]当 i >= 1时 还是只能选择一种
这里由于是二维的考虑 j < i 的情况当 j < i 时选法就是 f[j][j] 大于j的数选不了
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, f[N][N];
int main(){
cin >> n;
f[0][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++){
if(j >= i) f[i][j] = (f[i-1][j] + f[i][j-i]) % mod; //don't select
else f[i][j] = f[j][j];
}
}
cout << f[n][n];
return 0;
}
算法2
降低至一维
C++ 代码
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n, 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];
return 0;
}