算法训练营day38 动态规划⑥ 322. 零钱兑换、279.完全平方数、139.单词拆分、多重背包

        动态规划的第六篇！背包问题总结篇！

322. 零钱兑换

        题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。但是如何找最小的“组合”呢？（通过dp数组的不同定义 与 递推公式）

  • 确定dp数组以及下标的含义

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

  • 确定递推公式

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

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

  • dp数组如何初始化

        首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

        其他下标对应的数值呢？考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

  • 确定遍历顺序

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

  1. 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  2. 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

  • 举例推导dp数组

        略

        以先遍历物品、后遍历背包为例

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:dp = [float('inf')] * (amount + 1)  # 创建动态规划数组，初始值为正无穷大dp[0] = 0  # 初始化背包容量为0时的最小硬币数量为0for coin in coins:  # 遍历硬币列表，相当于遍历物品for i in range(coin, amount + 1):  # 遍历背包容量# 注意这个for循环的“剪枝”if dp[i - coin] != float('inf'):  # 如果dp[i - coin]不是初始值，则进行状态转移dp[i] = min(dp[i - coin] + 1, dp[i])  # 更新最小硬币数量if dp[amount] == float('inf'):  # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解return -1return dp[amount]  # 返回背包容量为amount时的最小硬币数量

279.完全平方数

        题目翻译一下：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

  • 确定dp数组（dp table）以及下标的含义

        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]);

  • dp数组如何初始化

        dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0。

        从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]);中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

  • 确定遍历顺序

        最小组合，和上题一样

        所以本题外层for遍历背包，内层for遍历物品，还是外层for遍历物品，内层for遍历背包，都是可以的！

  • 举例推导dp数组

        略

class Solution:def numSquares(self, n: int) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1):  # 遍历背包for j in range(1, int(i ** 0.5) + 1):  # 遍历物品 # 注意对j的取值范围进行开根号的限制# 更新凑成数字 i 所需的最少完全平方数数量dp[i] = min(dp[i], dp[i - j * j] + 1)# 注意这个位置使用的是j * jreturn dp[n]

139.单词拆分

动态规划

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

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

  • 确定dp数组以及下标的含义

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

  • 确定递推公式

        如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

        所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  • dp数组如何初始化

        从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

  • 确定遍历顺序

        拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

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

        "apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

        所以说，本题一定是 先遍历 背包，再遍历物品。

        换而言之，就是题目中的字符串中单词元素可能出现在多个位置，所以不能先遍历物品，不然物品就被消耗掉了，按序遍历到后面就没有物品可用了

  • 举例推导dp[i]

        略

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)n = len(s)dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词dp[0] = True  # 初始状态，空字符串可以被拆分成单词for i in range(1, n + 1): # 遍历背包for j in range(i): # 遍历单词if dp[j] and s[j:i] in wordSet:dp[i] = True  # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词# 防止被覆盖breakreturn dp[n]

回溯解法

  • 递归终止条件
if startIndex >= len(s):return True
  • 递归逻辑
  1. 从 startIndex 开始，尝试所有可能的拆分位置 i
  2. 截取从 startIndex 到 i 的子串作为候选单词
  3. 如果这个候选单词在字典中存在，并且从 i+1 位置开始的剩余字符串也能被成功拆分（递归调用的结果为 True），则返回 True
class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) -> bool:# 边界情况：已经遍历到字符串末尾，返回Trueif startIndex >= len(s):return True# 遍历所有可能的拆分位置for i in range(startIndex, len(s)):word = s[startIndex:i + 1]  # 截取子串if word in wordSet and self.backtracking(s, wordSet, i + 1):# 如果截取的子串在字典中，并且后续部分也可以被拆分成单词，返回Truereturn True# 无法进行有效拆分，返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) -> bool:wordSet = set(wordDict)  # 转换为哈希集合，提高查找效率return self.backtracking(s, wordSet, 0)

多重背包（了解即可）

        之前我们学了01背包、完全背包，现在我们来看一下多重背包的概念和题目

56. 携带矿石资源（第八期模拟笔试）

        多重背包和01背包是非常像的， 为什么和01背包像呢？每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

C, N = input().split(" ")
C, N = int(C), int(N)# value数组需要判断一下非空不然过不了
weights = [int(x) for x in input().split(" ")]
values = [int(x) for x in input().split(" ") if x]
nums = [int(x) for x in input().split(" ")]dp = [0] * (C + 1)
# 遍历背包容量
for i in range(N):for j in range(C, weights[i] - 1, -1):for k in range(1, nums[i] + 1):# 遍历 k，如果已经大于背包容量直接跳出循环if k * weights[i] > j:breakdp[j] = max(dp[j], dp[j - weights[i] * k] + values[i] * k) 
print(dp[-1])

背包问题总结篇

背包递推公式

        问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

  • 动态规划：416.分割等和子集(opens new window)
  • 动态规划：1049.最后一块石头的重量 II(opens new window)

        问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

  • 动态规划：494.目标和(opens new window)
  • 动态规划：518. 零钱兑换 II(opens new window)
  • 动态规划：377.组合总和Ⅳ(opens new window)
  • 动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

        问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ，对应题目如下：

  • 动态规划：474.一和零(opens new window)

        问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ，对应题目如下：

  • 动态规划：322.零钱兑换(opens new window)
  • 动态规划：279.完全平方数

遍历顺序

  • 01背包：

        一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的

  • 完全背包

        题目稍有变化，两个for循环的先后顺序就不一样了。相关题目如下：

  1. 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
  2. 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

  • 求组合数：动态规划：518.零钱兑换II(opens new window)

  • 求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

        如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

  • 求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/diannao/93951.shtml
繁体地址，请注明出处：http://hk.pswp.cn/diannao/93951.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

vue+element 实现下拉框共享options

vue+element 实现下拉框共享options

背景 用户的需求总是多样的&#xff0c;这不用户想做个下拉连选&#xff0c;每选一个基金&#xff0c;下方表格多一行&#xff0c;选择对应的重要性&#xff0c;任务&#xff1b;问题 其他都好弄&#xff0c;任务是远程搜索&#xff0c;选择人的单选下拉&#xff0c;如果每个下…
阅读更多...
centos服务器安装minio

centos服务器安装minio

1.创建目录和下载文件 #创建相关文件夹 mkdir -p /home/minio mkdir -p /home/minio/bin mkdir -p /home/minio/data#进入上面创建的bin目录下 cd /home/minio/bin#下载minio&#xff08;最新版minio无法通过页面的控制台配置accesskey建议选择2024年的版本操作&#xff09; ht…
阅读更多...
【云故事探索】NO.16：阿里云弹性计算加速精准学 AI 教育普惠落地

【云故事探索】NO.16：阿里云弹性计算加速精准学 AI 教育普惠落地

智能精准学寒雪老师 X 阿里云弹性计算&#xff1a;以坚实算力底座&#xff0c;实现 AI 一对一教育普惠的愿景 【导语】 当全球首个 K12 教育超级智能体“寒雪老师”在深夜为万千学子答疑解惑&#xff0c;支撑其流畅互动的&#xff0c;是阿里云弹性计算 15 年淬炼的坚实算力底座…
阅读更多...
forge篇——配置

forge篇——配置

从这篇文章开始，我们开始研究forge代码，以下是forge源代码和代码解析 ForgeConfigSpec 类详细解析 ForgeConfigSpec 是 Minecraft Forge 模组开发中的核心配置类，基于 NightConfig 库实现，提供了类型安全、验证和自动纠正功能。以下是关键部分的详细解释： 1. 类定义与基…
阅读更多...
全新发布｜知影-API风险监测系统V3.3，AI赋能定义数据接口安全新坐标

全新发布｜知影-API风险监测系统V3.3，AI赋能定义数据接口安全新坐标

7月31日&#xff0c;全知科技「知影-API风险监测系统V3.3」版本正式上线。在版本发布直播中&#xff0c;全知科技资深产品经理裴向南系统讲解了V3.3版本的核心亮点、能力升级与后续产品规划方向。作为全知科技自主研发的核心产品&#xff0c;「知影-API风险监测系统」自2017年起…
阅读更多...
动作捕捉技术重塑具身智能开发：高效训练与精准控制的新范式

动作捕捉技术重塑具身智能开发：高效训练与精准控制的新范式

具身智能&#xff08;Embodied AI&#xff09;是指智能体通过与环境交互实现感知、学习和决策的能力&#xff0c;其核心在于模拟人类或生物的形态与行为。具身智能的发展意义在于突破传统AI的局限性&#xff0c;使机器能够适应复杂多变的真实场景&#xff0c;从而在工业制造、医…
阅读更多...
【Andriod Studio】勾选不了Android SDK，提示unavailable

【Andriod Studio】勾选不了Android SDK，提示unavailable

首先&#xff0c;直接说结论——网络&#xff08;代理&#xff09;有问题 先看第一个文章里面说的&#xff0c;https://blog.csdn.net/weixin_53485880/article/details/128200878 要确定自己没有开启代理&#xff08;就是Set proxy里选cancel&#xff09;&#xff0c;安装SDK…
阅读更多...
数据结构与算法——字典（前缀）树的实现

数据结构与算法——字典（前缀）树的实现

参考视频&#xff1a;左程云--算法讲解044【必备】前缀树原理和代码详解 类实现&#xff1a; class Trie {private:class TrieNode {public:int pass;int end;vector<TrieNode*> nexts;TrieNode(): pass(0), end(0), nexts(26, nullptr) {}};TrieNode* root; // 根指针…
阅读更多...
STORM代码阅读笔记

STORM代码阅读笔记

默认的 分辨率是 [160,240] &#xff0c;基于 Transformer 的方法不能做高分辨率。 Dataloader 输入是 带有 pose 信息的 RGB 图像 eval datasets ## 采样帧数目 20 num_max_future_frames int(self.timespan * fps) ## 每次间隔多少个时间 timesteps 取一个context image n…
阅读更多...
2025电赛G题-发挥部分-参数自适应FIR滤波器

2025电赛G题-发挥部分-参数自适应FIR滤波器

&#xff08;1&#xff09;测评现场提供由RLC元件&#xff08;各1个&#xff09;组成的“未知模型电路”。 按照图3所示&#xff0c;探究装置连接该电路的输入和输出端口&#xff0c;对该电路进行 自主学习、建模&#xff08;不可借助外部测试设备&#xff09;&#xff0c;2分钟…
阅读更多...
Linux基础 -- 内核快速向用户态共享内核变量方案之ctl_table

Linux基础 -- 内核快速向用户态共享内核变量方案之ctl_table

系统化、可直接上手的 /proc/sys sysctl 接口使用文档。内容涵盖&#xff1a;机制原理、适用场景、ctl_table 字段详解、常用解析器&#xff08;proc_handler&#xff09;完整清单与选型、最小样例到进阶&#xff08;范围校验、毫秒→jiffies、字符串、数组、每网络命名空间&a…
阅读更多...
【RH124知识点问答题】第3章 从命令行管理文件

【RH124知识点问答题】第3章 从命令行管理文件

1. 怎么理解“Linux中一切皆文件”&#xff1f;Linux是如何组织文件的&#xff1f;&#xff08;1&#xff09;“Linux中一切皆文件”的理解和文件组织&#xff1a;在Linux中&#xff0c;“一切皆文件”指的是Linux将各种设备、目录、文件等都视为文件对象进行管理。这种统一的文…
阅读更多...
练习javaweb+mysql+jsp

练习javaweb+mysql+jsp

只是简单的使用mysql、简单的练习。 有很多待完善的地方&#xff0c;比如list的servlet页面&#xff0c;应该判断有没有用户的。 比如list.jsp 应该循环list而不是写死 index.jsp 样式可以再优化一下的。比如按钮就特丑。 本文展示了一个简单的MySQL数据库操作练习项目&#x…
阅读更多...
使用Nginx部署前端项目

使用Nginx部署前端项目

使用Nginx部署前端项目 一、总述二、具体步骤 2.1解压2.2将原来的html文件夹的文件删除&#xff0c;将自己的静态资源文件放进去&#xff0c;点击nginx.exe文件启动项目2.3查看进程中是否有ngix的两个进程在浏览器中输入“localhost:端口号”即可访问。 2.4端口被占用情况处理 …
阅读更多...
【论文学习】KAG论文翻译

【论文学习】KAG论文翻译

文章目录KAG: Boosting LLMs in Professional Domains via Knowledge Augmented Generation摘要1 引言2 方法论2.1 LLM友好型知识表示2.2 互索引机制2.2.1 语义分块2.2.2 带丰富语境的的信息抽取2.2.3 领域知识注入与约束2.2.4 文本块向量与知识结构的相互索引2.3 逻辑形式求解…
阅读更多...
24黑马SpringCloud安装MybatisPlus插件相关问题解决

24黑马SpringCloud安装MybatisPlus插件相关问题解决

目录 一、前言 二、菜单栏没有Other 三、Config Database里的dburl需要加上时区等配置 一、前言 在学习24黑马SpringCloud的MybatisPlus-12.拓展功能-代码生成器课程时&#xff0c;发现由于IDEA版本不同以及MybatisPlus版本更新会出现与视频不一致的相关问题&#xff0c;本博…
阅读更多...
人工智能赋能聚合物及复合材料模型应用与实践

人工智能赋能聚合物及复合材料模型应用与实践

近年来&#xff0c;生成式人工智能&#xff08;包括大语言模型、分子生成模型等&#xff09;在聚合物及复合材料领域掀起革命性浪潮&#xff0c;其依托数据驱动与机理协同&#xff0c;从海量数据中挖掘构效关系、通过分子结构表示&#xff08;如 SMILES、BigSMILES&#xff09;…
阅读更多...
MyBatis-Plus3

MyBatis-Plus3

一、条件构造器和常用接口 1.wapper介绍 MyBatis-Plus 提供了一套强大的条件构造器&#xff08;Wrapper&#xff09;&#xff0c;用于构建复杂的数据库查询条件。Wrapper 类允许开发者以链式调用的方式构造查询条件&#xff0c;无需编写繁琐的 SQL 语句&#xff0c;从而提高开…
阅读更多...
GXP6040K压力传感器可应用于医疗/汽车/家电

GXP6040K压力传感器可应用于医疗/汽车/家电

GXP6040K 系列压力传感器是一种超小型&#xff0c;为设备小型化做出贡献的高精度半导体压力传感器&#xff0c;适用于生物医学、汽车电子、白色家电等领域。采用标准的SOP6 和 DIP6 封装形式&#xff0c;方便用户进行多种安装方式。 内部核心芯片是利用 MEMS&#xff08;微机械…
阅读更多...
Android ConstraintLayout 使用详解

Android ConstraintLayout 使用详解

什么是 ConstraintLayoutConstraintLayout&#xff08;约束布局&#xff09;是 Android Studio 2.2 引入的一种新型布局&#xff0c;现已成为 Android 开发中最强大、最灵活的布局管理器之一。它结合了 RelativeLayout 的相对定位和 LinearLayout 的线性布局优势&#xff0c;能…
阅读更多...
最新文章

Copyright @ 2022~2023