1362 - 零钱兑换II
时间限制 : 1 秒
内存限制 : 128 MB
给你一个整数数组 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 <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000