零钱兑换II

Leetcode Link: 518. 零钱兑换 II - 力扣（LeetCode）

题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。

本道题从开始的时候没有想出来，暴力递归也没想出来

从暴力递归到动态规划

暴力递归

重点学习本题子问题的可能情况讨论

子问题的输入和 01背包 的问题类似，但是由于本题是 完全背包 ，即每个位置上的东西可重复利用，因此子问题的分解情况是不同的，但是从左到右的尝试模型。

该题的子问题的分解情况是：选 0 个当前位置 coin，选 1 个，选 2 个… 直到溢出。 在这种分解情况下，一定能够保证下一个子问题传入的位置是 idx+1

能不能这样说，所有从左到右的尝试模型，必需每次都走，并且必需穷举所有的可能性情况

类似的，01背包的子问题分解是选或者不选，是本问题的特殊情况，即选0个当前位置，选1个当前位置

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        res = self.process(coins, 0, amount)
        return res
    
    # 子问题可能情况：对于第idx位的面值，选多少张？
    # 可以保证下一个问题一定走到了idx+1的位置
    def process(self, coins, idx, rest):
        if rest == 0:
            return 1
        if idx == len(coins) or rest < 0: # 这里可以简化为 idx == len(coins)
            return 0
        
        nums = 0 # 当前位的钱币选择多少张
        p = 0
        while( rest-coins[idx]*nums >=0): # 这里控制了送进去的不会rest<0，所以可以减少一个base case
            p += self.process(coins, idx+1, rest-coins[idx]*nums)
            nums += 1
        return p

如果提前控制的送入的参数，即可减少base case（一般是不等号的 base case），为了避免改写dp时混乱，感觉

• 动态规划

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # [len(coins)+1, amount+1]
        dp = [[0 for _ in range(amount+1)] for _ in range(len(coins)+1)]
        # 填写base case
        for i in range(len(coins)+1):
            dp[i][0] = 1
        for i in range(len(coins)-1,-1,-1):
            for j in range(1, amount+1):
                nums = 0
                while(j-coins[i]*nums>=0):
                    dp[i][j] += dp[i+1][j-coins[i]*nums]
                    nums += 1
        return dp[0][amount]

Warning

从暴力递归中可以发现一个base case是 idx==len(coins)，为了这个base case能够体现在dp中(取的到且有值)，需要初始化时令其行数为[..] for _ in range(len(coins)+1)] 但是，如果直接按照这个的结果去填写dp中的行，是会溢出的（当i取到len(coins)时coins[i]报错），故正确的是for i in range(len(coins)-1,-1,-1)。 可以看到，第一个取到的值是len(coins)-1而不是len(coins)。也就是说，dp的最后一行我们白定义了（没用上），这里是一个逻辑不一致的地方

本题求一个格子的时间复杂度不再是 $O(1)$，而有一个 for 循环，这是和前面的从左到右的尝试模型的巨大区别！

如果计算一个格子没有枚举行为(for循环，本题就是)，记忆化搜索和动态规划的严格表结构的算法一样好 如果有，那么就是严格表结构（dp，动态规划）的更好。

• 状态压缩 可以看到第i行只和第i+1行有关，因此最多需要两行就行。 后发现一行也行，因为依赖的列位置是固定的，都在当前列的前面，倒着来就可以了。

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # [len(coins)+1, amount+1]
        dp = [[0 for _ in range(amount+1)] for _ in range(len(coins)+1)]
        # 填写base case
        for i in range(len(coins)+1):
            dp[i][0] = 1
        for i in range(len(coins)-1,-1,-1):
            for j in range(1, amount+1):
                dp[i][j] = dp[i+1][j]
                if  j-coins[i]>=0:
                    dp[i][j] += dp[i][j-coins[i]]
	                
        return dp[0][amount]

• 继续压缩

画出严格表结果，假设 i 位置的面值是 3 元，假设看第 14 列依赖哪些位置 显然 dp[i][14]=dp[i+1][14]+dp[i+1][11]+dp[i+1][8]+dp[i+1][5]+dp[i+1][2] (11 = 14-3x1)

而我们再看看⭐号位置 (dp[i][11]) 依赖哪些位置？ 依赖的是 dp[i][11]=dp[i+1][11]+dp[i+1][8]+dp[i+1][5]+dp[i+1][2]

显然这里就出现了重复，我们可以去掉这种多余的枚举行为，即 dp[i][14]=dp[i][11]+dp[i+1][14]

这就是为什么要建立空间感的原因！枚举填写格子的时候画两个试试！

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0 for _ in range(amount+1)]
        # 填写base case
        dp[0] = 1
        for i in range(len(coins)-1,-1,-1):
            for j in range(amount, -1, -1):
                nums = 0
                res = 0
                while(j-coins[i]*nums>=0):
                    res += dp[j-coins[i]*nums]
                    nums += 1
                dp[j] = res
        return dp[amount]
    

• 进一步压缩成一维的 dp

注意更新方向

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        # [len(coins)+1, amount+1]
        dp = [0 for _ in range(amount+1)]
        # 填写base case
        for i in range(len(coins)+1):
            dp[0] = 1
        for i in range(len(coins)-1,-1,-1):
            for j in range(1, amount+1):
                if  j-coins[i]>=0:
                    dp[j] += dp[j-coins[i]]
	                
        return dp[amount]

解法二

思路： 代码随想录的思路没看

题解：

解法三

思路：

题解：

启发和联系