第零章：经典动态规划：完全背包问题

labuladong经典动态规划：完全背包问题

---

动态规划之背包汇总

第零章：动态规划解题套路框架
第一章：经典动态规划：0-1 背包问题
第零章：经典动态规划：子集背包问题
第零章：经典动态规划：完全背包问题

---

0-1背包	完全背包
当前的物品放还是不放	当前的物品放还是不放，如果放，放几个（每种物品有无数个，可以无限次选取）

dp[i][j]数组的含义：dp[i][j] 表示对前i个物品，背包容量为j时，可以凑的硬币组合数（dp数组可以加一行一列表示0物品或0容量时的状态，更便于进行状态转移）

• 0-1 背包时，对第i行的硬币coins[i-1] ,若选择该硬币，则dp[i][j]=dp[i-1][j-coins[i-1]] (因为每种硬币只有一枚，所以状态是从上一枚硬币转到当前硬币)
• 完全背包时，对第i行的硬币coins[i-1] ,若选择该硬币，则dp[i][j]=dp[i][j-coins[i-1]] （因为硬币有无数枚，选完当前硬币可以再选当前硬币）。
  • 选的时候为dp[i][j-coins[i-1]]，选coins[i-1]时，总的金额减少到j-coins[i-1],但由于是完全背包问题，每个物品可以选无限次，所以，剩下的可以选的硬币还应该是coins[0...i-1]前i个

518. 零钱兑换 II

class Solution(object):
    def change(self, amount, coins):
        n=len(coins)

        # 行和列都分别增加1，第0列表示背包容量为0，第一行表示（虚拟）物品重量为0
        # 这样做，方便初始化dp数组以及后续dp状态转移
        dp=[[0 for _ in range(amount+1)] for _ in range(n+1)]
        for t in range(len(coins)+1):
            dp[t][0]=1

        for i in range(1,n+1):
            for j in range(1,amount+1):
                # 如果该物品重量超过容量，肯定不能放
                if j<coins[i-1]:
                    dp[i][j]=dp[i-1][j]
                # 如果没有超过重量，则有两种情况
                # 1. （不放当前的商品）之前的物品已经凑齐:dp[i-1][j]
                # 2. (放当前的商品) 比如用[1,2]凑5，已经知道了[1,2]凑（5-2）的方法，
                #     则把现在的2放进去就可以：dp[i][j-coins[i-1]]. (2可以多次使用)
                else:
                    dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]]
        return dp[-1][-1]