"力扣500题笔记5：零钱兑换 II动态规划解析"

根据题目要求，我们需要计算并返回可以凑成总金额的硬币组合数。给出一个整数数组coins表示不同面额的硬币，和一个整数amount表示总金额。假设每种面额的硬币有无限个。如果任何硬币组合都无法凑出总金额，则返回0。 我们可以使用动态规划的思路来解决这个问题，具体采取完全背包的方法。我们定义一个二维数组f来保存问题的状态，其中f[i][j]表示从前i种硬币中选，并且总金额恰好为j的所有选法集合的方案数。那么f[n][amount]表示从前n种硬币中选，并且总金额恰好为amount的所有选法集合的方案数，也即为答案。 我们可以进行集合划分，将问题进行拆分。首先我们需要遍历硬币数组coins，对于每个硬币的面额coin，我们需要计算出选取k个硬币coin能凑出金额为j的所有选法集合的方案数。那么f[i][j]可以通过选择或者不选择第i个硬币来得到。如果我们选择了第i个硬币coin，那么问题规模就变成了选取i个硬币coin凑出金额为j-coin的所有选法集合。如果我们不选择第i个硬币coin，那么问题规模就变成了选取i-1个硬币coin凑出金额为j的所有选法集合。因此我们可以得到状态转移方程： f[i][j] = f[i-1][j] + f[i][j-coin] 接下来我们需要考虑边界情况。当金额为0时，由于我们可以选择不选取任何硬币，因此f[i][0]的值都为1。而当硬币种类为0时，无法凑出任何金额，因此f[0][j]的值都为0。 最后，我们可以通过动态规划的方法，使用一个二层循环来计算所有状态的值。外层循环遍历硬币数组coins，内层循环遍历总金额amount。最终我们将得到f[n][amount]的值，即为所求的结果。 举个例子来说明：假设amount=5，coins=[1, 2, 5]。我们先初始化一个大小为6x6的二维数组f，其中f[i][j]表示从前i种硬币中选，并且总金额恰好为j的所有选法集合的方案数。初始时，我们将所有元素的值都设置为0。 当i=0时，表示从前0种硬币（也即没有硬币可选）中选，那么无论总金额为多少，都无法凑出，因此f[0][j]都为0。 当j=0时，表示要凑出的总金额为0，我们可以选择不选取任何硬币，因此f[i][0]都为1。 接下来，我们开始进行状态转移。首先考虑使用第一种面额的硬币1，当考虑的金额为1时，我们可以选择不选取硬币，也可以选择选择1个硬币。因此有两种选择，即f[1][1]=f[0][1]+f[1][1-1]=0+1=1。同理，当金额为2时，我们可以选择不选取硬币，也可以选择选择2个硬币。因此有两种选择，即f[1][2]=f[0][2]+f[1][2-1]=0+1=1。当金额为3时，我们可以选择不选取硬币，也可以选择选择3个硬币。因此有两种选择，即f[1][3]=f[0][3]+f[1][3-1]=0+1=1。同理可得，f[1][4]=1，f[1][5]=1。 接下来考虑使用第二种面额的硬币2，当考虑的金额为1时，我们无法凑出，因此f[2][1]=f[1][1]=1。当金额为2时，我们可以选择不选取硬币，也可以选择选择2个硬币。因此有两种选择，即f[2][2]=f[1][2]+f[2][2-2]=1+1=2。同理可得，f[2][3]=f[1][3]+f[2][3-2]=1+0=1，f[2][4]=f[1][4]+f[2][4-2]=1+1=2，f[2][5]=f[1][5]+f[2][5-2]=1+1=2。 最后考虑使用第三种面额的硬币5，当考虑的金额为1时，我们无法凑出，因此f[3][1]=f[2][1]=1。当金额为2时，我们无法凑出，因此f[3][2]=f[2][2]=2。当金额为3时，我们可以选择不选取硬币，也可以选择选择3个硬币。因此有两种选择，即f[3][3]=f[2][3]+f[3][3-5]=1+0=1。同理可得，f[3][4]=f[2][4]+f[3][4-5]=2+0=2，f[3][5]=f[2][5]+f[3][5-5]=2+1=3。 最终我们得到f[3][5]=3，即从前3种硬币种类中选，并且总金额恰好为5的所有选法集合的方案数为3。这也即是我们所求的结果。 总之，根据动态规划的思路，我们可以通过二维数组f来计算并保存每个子问题的状态，最终得到f[n][amount]的值，即为可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，则返回0。通过该方法，可以保证结果符合32位带符号整数的要求。 综上所述，我们可以通过动态规划的完全背包方法来解决该问题。算法的时间复杂度为O(n*amount)，空间复杂度为O(n*amount)。