LeetCode解法汇总518. 零钱兑换 II
目录链接：
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目：
https://github.com/September26/java-algorithms
原题链接：. - 力扣（LeetCode）
描述：
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10] 输出：1
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
解题思路：
使用动态规划，amoutDp[i]代表到总额为i时所有的组合可能。
正常来说，我们会先求1，在求2，3。但是这样会有一个问题，以amout=5，coins=[1,2,5]为例。当i=3时，3=1+2和3=2+1，这两个很明显重复了，导致重复计算。
所以，我们需要换一种思路，首先求仅使用1求[1,5]范围内每个位置有多少种可能，然后使用1,2求[2,5]范围内每个位置有多少种可能，最后使用[1,2,5]求[5,5]范围内有多少种可能。这样就确定了顺序，确保不会存在先选后选的问题。
代码：
class Solution518
{
public:int change(int amount, vector<int> &coins){vector<int> amountDp(amount + 1, 0);amountDp[0] = 1;for (int coin : coins){for (int i = coin; i <= amount; i++){amountDp[i] += amountDp[i - coin];}cout << amountDp.size() << endl;}return amountDp[amount];}
};