1362 - 零钱兑换II
Time Limit : 1 秒
Memory Limit : 128 MB
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并输出可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，输出 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
Input
第一行为1个整数n，表示coins的长度
第二行为n个整数，表示硬币面额
第三行为1个整数amount，表示总金额
Output
可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，输出 0
Examples
Input
3 1 2 5 5
Output
4
Input
1 2 3
Output
0
Input
1 1 0
Output
1
Hint
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000