思路1:转换为完全背包问题
将问题看待为,从1~n中挑选物品,每种物品个数不限,求总体积恰好为n的选法数量
状态表示 f[i][j]:
集合:表示所有从1…i中选,总体积恰好为j的选法集合
属性:选法数量
状态计算:
依据完全背包问题的思路,将f[i][j]按照第i个物品选几个划分为k类;
状态表达式:
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2 * i] + ...;
化简思路:
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];//因为有s*i<=j的限制,所以最后一项相等
得到:
f[i][j] = f[i - 1][j]+f[i][j-i];
非常容易搞错的初值问题:
在完全背包问题中,求最大值时,当都不选时,价值显然是 0
而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1
即:for (int i = 0; i <= n; i ++) f[i][0] = 1;
等价变形后: f[0] = 1
朴素解法:
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N][N];
int n;
int main(){
cin>>n;
for (int i = 0; i <= n; i ++) f[i][0] = 1;//求最大值时,当都不选时,价值显然是 0
//而求方案数时,当都不选时,方案数是 1(即前 i 个物品都不选的情况也是一种方案),所以需要初始化为 1
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j]%mod;
if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
}
cout<<f[n][n]<<endl;
return 0;
}
模仿背包问题进行优化:
// f[i][j] = f[i - 1][j] + f[i][j - i]
#include <iostream>
using namespace std;
const int N = 1e3 + 7, mod = 1e9 + 7;
int f[N];
int main() {
int n;
cin >> n;
f[0] = 1; // 容量为0时,前 i 个物品全不选也是一种方案
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;
}
思路2:计数dp问题
状态表示f[i][j]:所有总和是i,并且恰好表示成j个数的和的方案
状态计算:
根据f[i][j]代表的方案中最小元素是不是1,将集合划分为:
f[i-1][j-1]和f[i-j][j]
f[i-j][j]表示每一个数都减去一个1 因为所求属性是数量,所以每一个数都减去一个1后方案是一一对应的
初值问题:
f[0][0]表示总和是0,0个数表示,所以赋值为1(1种方案)
最终计算结果时,ans=f[n][1]+f[n][2]...+f[n][n]
可选数字数最大为n
计数dp代码:
#include <iostream>
#include <algorithm>
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 ans=0;
for(int i=1;i<=n;i++)
ans=(ans+f[n][i])%mod;
cout<<ans<<endl;
return 0;
}