518. 零钱兑换 II

https://leetcode-cn.com/problems/coin-change-2/

解法一：暴力dfs递归（超时）

为防止重复，dfs函数设一个start，每次从start向后循环（不回头）

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        self.res = 0
        self.dfs(amount, coins, 0, 0)
        return self.res
    
    def dfs(self, amount, coins, sum, start):
        if sum > amount:
            return
        elif sum == amount:
            self.res += 1
        for i in range(start, len(coins)):
            self.dfs(amount, coins, sum + coins[i], i)

解法二：dp

dp[i][j] 的定义如下： 若只使用前 i 个物品（可以重复使用），当背包容量为 j 时，有dp[i][j] 种方法可以装满背包。 i=0表示不取，因此对coins从1开始遍历，i对应coins[i-1] 状态转移：

dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
			装入第i个      不装第i个

dp[i][j] 的值应该是以上两种选择的结果之和 base case：

dp[0][j]=0	#一个数都不取
dp[i][0]=1	#凑出0

第二条比较难理解，也是dp的关键。 为啥凑0也算一种凑法？例如5=0+5也算一种，因此dp[i][0]=1虽然第二个状态看上去是0，在迭代中实际操作是取单个第i个数，所以也算一种

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n=len(coins)
        dp=[[0]*(amount+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0] = 1	#关键
        for i in range(1,n+1):
            for j in range(amount+1):
                if j-coins[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][amount]