算法: 硬币找零 II 518. Coin Change 2

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• All the values of coins are unique.
• 0 <= amount <= 5000

1. 最优动态规划解法

需要注意：解决方案顺序无关，比如dp[3] = 1 + 2, 跟 dp[3] = 2 + 1 是一种解决方案。
两个for循环的顺序不能调换。
排序可以省略coins.sort()， 因为想一下，一个数字i，遍历一轮只能有一个coin == i

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        # coins.sort()
        for coin in coins:
            for i in range(coin, amount + 1):
                if i >= coin:
                    dp[i] += dp[i-coin]
        return dp[-1]

2. 二维数组 动态规划解法

让我们dp_sum[i][j]用多种方式来表示金额i，以便我们只使用第j一枚硬币。我们用 初始化这个表的第一列1，因为我们可以说有一种方法可以得到amount = 0，使用第一个j硬币：不要拿任何硬币。
要找到dp_sum[i][j]我们需要查看最后一枚硬币，它由两个术语组成：

1. dp_sum[i][j-1], 选项数量，我们只取第一个j-1硬币
2. dp_sum[i-coins[j]][j]，选项数量，我们删除了硬币数量j，我们需要找到剩余数量的选项数量。
   示例：让我们考虑coins = [1,2,5] amont = 5。那么 table dp_sum将等于
   

复杂的时间和空间是O(amount *N)，其中N是不同硬币的数量，因为我们只O(1)需要更新每个单元格。

在代码中，我使用 index i+1而不是i，因为我们从1st 列开始，而不是0th。

更新空间复杂度可以降低到O(amount)，因为对于每一次j我们最多看一排。

class Solution:
    def change(self, amount, coins):
        N = len(coins)
        if N == 0: return int(N == amount)
        
        dp_sum = [[0] * N for _ in range(amount + 1)]
        for i in range(N): dp_sum[0][i] = 1
        
        for i,j in product(range(amount), range(N)):
            dp_sum[i+1][j] = dp_sum[i+1][j-1]
            if i+1 - coins[j] >= 0:
                dp_sum[i+1][j] += dp_sum[i+1-coins[j]][j]           
                    
        return dp_sum[-1][-1]

参考

https://leetcode.com/problems/coin-change-2/discuss/99210/python-O(n)-space-dp-solution

https://leetcode.com/problems/coin-change-2/discuss/675096/Python-O(amount-*-N)-simple-dp-explained-(updated)