y总的DP算法思路
1)状态表示$f_{i,j}$
1.1 集合:所有从1-i中选择,并且总钱数为j的方案的集合
1.2 属性(为要求解的东西)
(2)状态计算–对应集合的划分
(将集合划分成各个子集,然后逐个击破)如:按照第i个货币选择0,1,2……k个来进行划分
第一个子集:意味着第i个货币不选择,从1-(i-1)选择总钱数为j的集合,恰好就是$f_{i-1,j}$。
…
第k+1个子集:意味着第i个货币选了k个,恰好为$f_{i-1,j-(ki)}$
所以得到:
$$
f_{i,j} = f_{i-1,j}+f_{i-1,j-v_i}+…f_{i-1,j-kv_i}
$$
其中$k_{max} =j/v_i$。取整数
观察得到
$$
f_{i,j-v_i} = f_{i-1,j-v_i}+f_{i-1,j-2v_i}+…f_{i-1,j-kv_i}
$$
从而得到优化后的表达式:
$$
f_{i,j} = f_{i-1,j}+f_{i,j-v_i}
$$
#include <iostream>
using namespace std;
typedef long long LL;
const int N= 30,M = 10010;
LL f[N][M];
int n,m;
int main(){
cin >> n >> m;
f[0][0] = 1;
for(int i = 1; i<=n;i++){
int v;
cin >> v;
for(int j = 0; j<=m; j++){
f[i][j] = f[i-1][j];
if(j>=v)
f[i][j] += f[i][j-v];
}
}
cout << f[n][m];
return 0;
}
#include <iostream>
using namespace std;
typedef long long LL;
const int N= 30,M = 10010;
LL f[N][M];
int n,m;
int main(){
cin >> n >> m;
f[0][0] = 1;
for(int i = 1; i<=n;i++){
int v;
cin >> v;
for(int j = 0; j<=m; j++){
f[i][j] = f[i-1][j];
if(j>=v)
f[i][j] += f[i][j-v];
}
}
cout << f[n][m];
return 0;
}