非压缩版(二维DP)
思路:可以当做是完全背包问题。其中需要凑出来的数看做背包的容量n,物品的体积为1~n,且每种物品都有无数个。
#include<iostream>
using namespace std;
//【重要】f[i][j]表示i个数的和为j的可能性
//如果选择第i个数,相当于选择值i。
const int N = 4010;
unsigned f[N][N];
int main() {
int n;
cin >> n;
for (int j = 0; j <= n; j++) f[1][j] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (j >= i)
for (int k = 1; k * i <= j; k++)
f[i][j] += f[i - 1][j - k * i];
}
}
cout << (f[n][n] - 1) % 2147483648u << endl;
return 0;
}
压缩版(一维DP)
#include<iostream>
using namespace std;
const int N = 4010;
unsigned f[N];
int main() {
int n;
cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
f[j] += f[j - i];
cout << (f[n] - 1) % 2147483648u << endl;
return 0;
}