首页 > 编程语言 >day50 动态规划part7 代码随想录算法训练营 322. 零钱兑换【什么时候+1】

day50 动态规划part7 代码随想录算法训练营 322. 零钱兑换【什么时候+1】

时间:2024-02-29 11:56:09浏览次数:31  
标签:背包 coins 随想录 322 amount 遍历 part7 inf dp

题目: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]

通过截图:

扩展写法:

资料:

  1. 零钱兑换  

如果求组合数就是外层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

相关文章

  • 今日补充练习-动态规划算法part7-卡尔57爬楼梯进阶
    注意点&感悟:多练习注意体会跟昨天的组合问题的区别。注意物品的边界题目链接:卡尔57爬楼梯进阶自己独立写的代码:#完全背包问题--下的求种类问题#物品是m,有限的#背包是ntotal,m=map(int,input().split())dp=[0]*(total+1)dp[0]=1forjinrange(total+1):......
  • day44 动态规划part7 代码随想录算法训练营 70. 爬楼梯 (进阶)
    题目:爬楼梯(进阶)-在卡尔网我的感悟:昨天最后没怎么听懂的,今日回旋镖来了。理解难点:递推公式,和遍历顺序手写笔记:代码示例:total,m=map(int,input().split())#每次爬m个#dp[i]含义是爬到i有dp[i]种方法#是完全背包问题dp=[0]*(total+1)dp[0]=1fo......
  • 代码随想录算法训练营第六天|242. 有效的字母异位词
    这个题目还是比较简单的,知道是查表的思路之后,很快就写出来了:classSolution:defisAnagram(self,s:str,t:str)->bool:iflen(s)!=len(t):returnFalsealphabet=[]dict_s={}dict_t={}foriinran......
  • 代码随想录算法训练营day08 | leetcode 344. 反转字符串、541. 反转字符串 II、54. 替
    目录题目链接:344.反转字符串-简单题目链接:541.反转字符串II-简单题目链接:[54.替换数字](题目页面(kamacoder.com))题目链接:151.反转字符串中的单词-中等题目链接:[55.右旋字符串](题目页面(kamacoder.com))题目链接:344.反转字符串-简单题目描述:编写一个函数,其作用是将......
  • 代码随想录 day64 柱状图中最大的矩形
    柱状图中最大的矩形本题和接雨水在很多地方都很相似但是不是求凹槽了而是求突起就是相同的思路求不同的柱体对于每一个柱体找左边最矮的柱体这个柱体的右边的柱体和这个柱体围成的矩形就为最大同理找右边的柱体这里注意要用while而不是if因为要找到最矮的而......
  • day44 动态规划part6 代码随想录算法训练营 518. 零钱兑换 II
    题目:518.零钱兑换II我的感悟:递推公式,我没写错。是初始化写错了。这种求多少种的,要考虑1种,是空集合选1中。而那些考虑能背最大的价值,要从0初始化,0的含义值无价值。 理解难点:递推公式,是累加dp[j]+=dp[j-conins[i]]初始化的含义 dp[0]=1听课笔记: 代码示例:cl......
  • day44 动态规划part6 代码随想录算法训练营 卡尔网52题
    题目:52.携带研究材料我的感悟:背模板,记下来,就好了。理解难点:听课笔记:代码示例:n,v=map(int,input().split())weight_list=[]value_list=[]for_inrange(n):weight,value=map(int,input().split())weight_list.append(weight)value_list.a......
  • day44 动态规划part6 代码随想录算法训练营 完全背包理论
    题目:完全背包理论我的感悟:记忆中理解。理解难点:为什么正序就是用多次?因为正序是借用本层左侧的状态,倒序是借用上一层的状态。演示:打印DP:示例代码:查看代码#01背包deftest_CompletePack1(weight,value,bagWeight):dp=[0]*(bagWeight+1)f......
  • day43 动态规划part5 代码随想录算法训练营 474. 一和零 【粗略理解】
    题目:474.一和零我的感悟:有点难想,加油、111本题没敲,有机会敲一遍理解难点:两个维度的背包听课笔记:代码示例:classSolution:deffindMaxForm(self,strs:List[str],m:int,n:int)->int:dp=[[0]*(n+1)for_inrange(m+1)]#创建二维动......
  • day43 动态规划part5 代码随想录算法训练营 494. 目标和
    题目:494.目标和我的感悟:加油!理解难点:dp的几种方法的应用记住dp[j]+=dp[j-nums[i]]听课笔记:代码示例:classSolution:deffindTargetSumWays(self,nums:List[int],target:int)->int:total_sum=sum(nums)ifabs(target)>total_sum:......