AcWing 278. 数字组合
原题链接
简单
作者:
rushhhhh
,
2021-02-11 14:08:06
,
所有人可见
,
阅读 311
二维写法
#include<iostream>
#include <climits>
using namespace std;
const int N = 10010;
int n, m;
int f[N][N];
// dp:
// 1、状态表示f[i,j]
// 1.1集合:所有从前i个物品中选,且总体积为j的选法的集合
// 1.2属性:count
// 2、状态计算
// f[i][j] = f[i-1][j-v] + ... + f[i-1][j], j从m到v
// 其中,f[i-1][j-v]表示选中第i个,即从前i-1个中选j-v体积有几种选法(加上第i个的体积v则总体积就是j)
// f[i-1][j]表示不选第i个,即从前i-1个中选满j体积有几种选法
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++)
{
int t = 0;
if(j >= v)
t += f[i-1][j-v];
t += f[i-1][j];
f[i][j] = t;
}
}
cout << f[n][m];
return 0;
}
一维写法
#include<iostream>
#include <climits>
using namespace std;
const int N = 10010;
int n, m;
int f[N];
// 一维写法:
int main()
{
cin >> n >> m;
f[0] = 1;
for (int i = 1; i <= n; ++i)
{
int v;
cin >> v;
for(int j=m; j>=v; j--)
{
f[j] += f[j-v];
// 即:
// int t = 0;
// t += f[j-v];
// t += f[j];
// f[j] = t;
}
}
cout << f[m];
return 0;
}