1362 - 零钱兑换II

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

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

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

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

输入

第一行为1个整数n,表示coins的长度

第二行为n个整数,表示硬币面额

第三行为1个整数amount,表示总金额

输出

可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,输出 0

样例

输入

3
1 2 5
5

输出

4

输入

1
2
3

输出

0

输入

1
1
0

输出

1

提示

  • 1 <= coins.length <= 300

  • 1 <= coins[i] <= 5000

  • coins 中的所有值 互不相同

  • 0 <= amount <= 5000

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题