A70760. 货币问题
编程题
入门
知识点
题目描述
某国家有 n 种不同面值的货币，第 i 种货币价值 a_i 元。
请问：如果每种货币都提供任意多的数量的情况下，如果需要 m 元金额的货币，有多少种不同的方案？
输入格式
第一行两个整数 n，m（m \le 5000，n \le 100)；
以下 n 行，每行一个整数，第 i+1 行为第 i 种货币的面值。
输出格式
一个整数，为方案数（方案数 \le 1018）。
输入输出样例
输入 #1
3 10 1 2 5
输出 #1
10
说明/提示
## 思路
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。
背包 DP：状态为容量（及物品），转移为选或不选当前物品。
## 步骤
1. 读入容量与物品体积/价值。
2. 按 01 或完全背包的循环顺序填 dp。
3. 输出最大价值或方案数。