算法1
(完全背包) $O(n^2)$
C++ 代码
// 完全背包
#include<iostream>
#include<cstdio>
using namespace std;
const int MOD = 1e9 + 7;
const int N = 1005;
int dp[N];
int n;
void solve() {
cin >> n;
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = i; j <=n; j++) {
dp[j] = (dp[j] + dp[j - i]) % MOD;
}
}
cout << dp[n] << endl;
}
signed main() {
solve();
return 0;
}