代码随想录训练营 Day38打卡 动态规划 part06 322. 零钱兑换 279. 完全平方数 139. 单词拆分

本文主要是介绍代码随想录训练营 Day38打卡 动态规划 part06 322. 零钱兑换 279. 完全平方数 139. 单词拆分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录训练营 Day38打卡 动态规划 part06

一、力扣322. 零钱兑换

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。
你可以认为每种硬币的数量是无限的。
示例
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

题目中说每种硬币的数量是无限的,可以看出是典型的完全背包问题。

dp[j]:凑足总额为j所需钱币的最少个数为dp[j]

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

本题求钱币最小个数,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数。

所以本题并不强调集合是组合还是排列。

以输入:coins = [1, 2, 5], amount = 5为例

在这里插入图片描述
dp[amount]为最终结果。

代码实现

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 创建一个长度为 amount + 1 的 dp 数组,初始值为正无穷大(表示当前金额不可达)dp = [float('inf')] * (amount + 1)# 初始化 dp[0] 为 0,因为凑出金额 0 需要 0 个硬币dp[0] = 0# 遍历每一种硬币面额for coin in coins:  # 遍历硬币,相当于遍历物品# 对于当前硬币面额 coin,遍历背包容量从 coin 到 amountfor i in range(coin, amount + 1):  # 遍历背包容量# 如果 dp[i - coin] 不是正无穷大,表示金额 (i - coin) 可达if dp[i - coin] != float('inf'):# 更新 dp[i],取使用当前硬币和不使用当前硬币两种情况中的最小值dp[i] = min(dp[i - coin] + 1, dp[i])# 检查 dp[amount] 是否仍为正无穷大# 如果是,则表示没有办法凑出总金额,返回 -1if dp[amount] == float('inf'):return -1# 否则,返回凑出总金额所需的最少硬币个数return dp[amount]

力扣题目链接
题目文章讲解
题目视频讲解

二、力扣279. 完全平方数

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

完全平方数就是物品(可以无限件使用),凑个正整数n就是背包,问凑满这个背包最少有多少物品?

dp[j]:和为j的完全平方数的最少数量为dp[j]

dp[j] 可以由dp[j - i * i]推出, dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j],所以递推公式:dp[j] = min(dp[j - i * i] + 1, dp[j]);

已输入n为5例,dp状态图如下:
在这里插入图片描述
最后的dp[n]为最终结果。

class Solution:def numSquares(self, n: int) -> int:# 初始化 dp 数组,长度为 n + 1,初始值为正无穷大# dp[j] 表示和为 j 的完全平方数的最少数量dp = [float('inf')] * (n + 1)# dp[0] = 0,因为和为 0 需要 0 个完全平方数dp[0] = 0# 遍历所有可能的完全平方数for i in range(1, int(n ** 0.5) + 1):  # i 表示当前完全平方数的根,如 1, 2, 3, ..., sqrt(n)square = i * i  # 计算完全平方数# 遍历背包容量(即要凑的目标和)for j in range(square, n + 1):  # j 表示当前目标和,从 square 到 n# 更新 dp[j],选择使用当前完全平方数后的最小值dp[j] = min(dp[j - square] + 1, dp[j])# 返回和为 n 的完全平方数的最少数量return dp[n]

力扣题目链接
题目文章讲解
题目视频讲解

三、力扣139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
示例
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词,说明就是一个完全背包!

dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

而本题其实我们求的是排列数,为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例,dp状态如图:

在这里插入图片描述
dp[s.size()]就是最终结果。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:# 将 wordDict 转换为一个集合,以便更快速地进行单词查找操作wordSet = set(wordDict)n = len(s)  # 获取字符串 s 的长度# 创建一个长度为 n + 1 的 dp 数组# dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分成字典中的单词dp = [False] * (n + 1)# dp[0] 表示空字符串,空字符串被认为可以被拆分成字典中的单词dp[0] = True# 遍历字符串的每个位置 i(从 1 到 n),相当于动态规划中的“背包容量”for i in range(1, n + 1):# 对于每个位置 i,检查从 0 到 i 的所有前缀 s[0:j] 是否可以被拆分for j in range(i):# 如果 s 的前 j 个字符可以被拆分成单词(dp[j] 为 True)# 并且 s[j:i] 这一段字符串在 wordSet 中存在,则 dp[i] 也为 Trueif dp[j] and s[j:i] in wordSet:dp[i] = True  # 更新 dp[i] 为 True,表示 s[0:i] 可以被拆分成字典中的单词break  # 找到一个有效拆分后,停止当前循环,进入下一个 i# 最后返回 dp[n],即字符串 s 的前 n 个字符(即整个字符串)是否可以被拆分成字典中的单词return dp[n]

力扣题目链接
题目文章讲解
题目视频讲解

这篇关于代码随想录训练营 Day38打卡 动态规划 part06 322. 零钱兑换 279. 完全平方数 139. 单词拆分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1106757

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d