题目:322. 零钱兑换
我的感悟:
- 看着文字版也能做出来了,哈哈哈!!
理解难点:
- 这题是最小值
dp[j] = min(dp[j],dp[j-coins[i]+1)
- 因为是数量要加一个1,有的加,有的不加,还没太搞清楚。
听课笔记:
代码示例:
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 求最小值了
# dp[j] = min(dp[j],dp[j-coins[i]])
# 没要求顺序,用外层是物品i,内层背包j
# 可以多次用正序
# 物品是coins集合,背包容量是amount
# 初始化float('inf')为因为是求最小
if amount ==0:
return 0
dp = [float('inf')] * (amount+1)
dp[0] = 0 # 这一步不能少
for i in range(len(coins)): # 外层物品
for j in range(coins[i],amount+1): # 内层背包
if j - coins[i] >=0 : # 只要不是inf就状态转移
dp[j] = min(dp[j],dp[j-coins[i]]+1)
if dp[amount] == float('inf'):
return -1
return dp[amount]
通过截图:
扩展写法:
资料:
- 零钱兑换
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
这句话结合本题 大家要好好理解。
视频讲解:https://www.bilibili.com/video/BV14K411R7yv
https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html
标签:背包,coins,随想录,322,amount,遍历,part7,inf,dp From: https://www.cnblogs.com/liqi175/p/18043178