经典算法 求解硬币组成问题

求解硬币组成问题

题目描述

实现一个算法求解组成硬币问题。介绍如下：

假设有面值给定的一些硬币，以及给定的总合值，问构成总合值的方法有多少种。

---

输入描述

• 第一行包含两个数字 N, M：
  • N 表示硬币面值的种类数
  • M 表示给定的总合值
• 第二行包含 N 个数字 Ai，表示每种硬币的面值。

数据范围：

• 1 ≤ N, M, Ai ≤ 1000
• 每种面值的硬币都有无限多个

---

输出描述

输出一行，为构成总合值的方法数。

---

输入输出样例

输入

3 3
1 2 3

输出

3

c++代码

#include<bits/stdc++.h>using namespace std;int main() {int N, M;cin >> N >> M;vector<int> dp(M + 1), arr(N);for (int i = 0; i < N; i++) cin >> arr[i];dp[0] = 1;for (int i = 0; i < N; i++) {for (int j = arr[i]; j <= M; j++) {dp[j] += dp[j - arr[i]];}}dp[0] = 0;cout << dp[M];return 0;
}//by wqs

算法解析

这个题目要求1 2和2 1是同一组合，所有我们规定第一层循环为前i个硬币而且，最后一个硬币是i的组合为多少，这样就不会出现2 1这样的情况了。