B. 零钱兑换II

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

给你一个整数数组 c 表示不同面额的硬币,另给一个整数 m 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

输入格式

第一行,包含2个整数 n 和 m,表示 数组 c 的元素个数、总金额

第二行,包含 n 个整数,表示数组 c 的 n 个面额

输出格式

可以凑成总金额的硬币组合数

样例

示例 1:

输入:

3 5
1 2 5

输出:

4

解释:有四种方式可以凑成总金额:

5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:

1 3
2

输出:

0

解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:

1 10
10 

输出:

1

数据范围与提示

1 <= n <= 300

1 <= c[i] <= 5000

c 中的所有值 互不相同

0 <= m <= 5000