零钱兑换

解题思路

   此题的思想应用了完全背包问题和求解背包方案数量问题，故需要将其转化为背包方案问题来求解。如下为推导公式：
   创建二维dp数组,$dp[i][j]$，表示使用零钱类数i和组成的总金额$j$。对于第$i$枚硬币金额为$c[i]$。对于$dp[i][j]$来说，可以不拿第i个硬币，就已经组成了总金额$j$。则此时$dp[i][j]=dp[i-1][j]$。当然如果拿取第i枚硬币，则总共会有1——k种方法，而需满足$0<=kc[i]<=j$ ，则状态转移方程如下：
$dp[i][j]=dp[i-1][j-c[i]]+dp[i-1][j-2c[i]]+...+dp[i-1][j-kc[i]]。$
   故对于总方案数来讲，将其两种方法加到一起得到:
$dp[i][j]=dp[i-1][j]$+$dp[i-1][j-c[i]]+dp[i-1][j-2c[i]]+...+dp[i-1][j-kc[i]$ （1）
   由于该方案是三重循环，故可以将其化简为两重循环，去除k的for循环判断。化简如下：
令j-c[i] =j,则原始可化简为:
$dp[i][j-c[i]]=$ $dp[i-1][j-c[i]]+dp[i-1][j-2c[i]]+dp[i-1][j-3c[i]]+...+dp[i-1][j-kc[i]+dp[i-1][j-(k+1)c[i]]$        (2)

   由于公式（1）和公式（2）中的红色部分是一样（调整k值），故将公式2带入到公式1中化简得到最终的状态转移方程：
$dp[i][j]=dp[i-1][j]+dp[i][j-c[i]]$

class Solution:
    def waysToChange(self, n: int) -> int:

        coins = [1,5,10,25]
        m = len(coins)
        
        dp = [[0]*(n+1) for i in range(m+1)]
        #初始化二维数组第一行,没有任何一种硬币，不论需要多少金额，都没有对应的方案数
        for i in range(n+1):
            dp[0][i] = 0
        #如果金额为0，对多少种硬币来说都是1种方案    
        for i in range(m+1):
            dp[i][0] = 1
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                #当总金额数j<金币额度时,则不拿第i个金币，因为金币coins下标从0开始，故需要coins[i-1]
                if  j<coins[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]+dp[i][j-coins[i-1]]
        return dp[-1][-1] % 1000000007 

本文地址：https://blog.csdn.net/jhsignal/article/details/109645710