题目描述
噜啦噜啦类,不完全 所有硬币组合问题。
不多说了 上代码
样例
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cstdio>
#include <queue>
#include <string>
#define int long long
#define endl '\n'
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int N = 10100;
const int value = 25;// 不同面值硬币的种类数
const int money = 10001;// 预设的最大金额
//const int coin = 10001;
int n, m;
int type[value];// 硬币的面值
int dp[money];// 用于存储每个金额对应的组合数
void solve() {
dp[0] = 1;// 金额为 0 时只有一种组合,即不选取硬币
for (int i = 0;i < n;i++) {
for (int j = type[i];j <= m;j++) {
// 更新动态规划数组,表示当前金额的组合数等于
//不选取当前硬币的组合数加上选取当前硬币的组合数
dp[j] = dp[j] + dp[j - type[i]];
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for (int i = 0;i < n;i++)
cin >> type[i];
solve();
cout << dp[m] << endl;
return 0;
}