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

news/2025/3/14 11:15:42/

目录

一、做题心得

二、题目与题解

题目一:322. 零钱兑换

题目链接

题解:动态规划--完全背包 

题目二: 279.完全平方数

题目链接

题解:动态规划--完全背包

题目三:139.单词拆分

题目链接

题解:动态规划--完全背包

三、小结


一、做题心得

今天来到了代码随想录动态规划章节的Part6,依旧是完全背包问题的应用。相对于前边直接套用模板,今天的题目难度相对较大一点,尤其是单词拆分这道题,bool型dp数组的使用,和之前做的题就有很大的不同。

话不多说,直接开始今天的内容。

二、题目与题解

题目一:322. 零钱兑换

题目链接

322. 零钱兑换 - 力扣(LeetCode)

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11输出:3解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104
题解:动态规划--完全背包 

这道题属于是完全背包求最值问题--求得凑成总金额所需的最少得硬币数量,当然,本质上讲,也是组合数问题。

首先就是dp数组的定义与初始化:dp[j]表示凑成金额 j 所需的最少硬币数量--注意:dp[j]必须初始化为一个较大的数,以防在后续min()函数处直接被初始值覆盖,还有就是初始化 dp[0] = 0

然后就是这道题的关键部分:如果存在一种或多种方式可以组成金额 j - coins[i],那么加上一个coins[i]之后就可以凑成金额 j。

这里直接看代码(含注释):

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount + 1, INT_MAX);        //dp[j]表示凑成金额 j 所需的最少硬币数量--注意:dp[j]必须初始化为一个最大的数,以防在后续min()函数处直接被初始值覆盖dp[0] = 0;          //初始化dp[0]为0,表示组成金额0不需要任何硬币for (int i = 0; i < coins.size(); i++) {            //先遍历物品再遍历背包(先遍历背包也可以)for (int j = coins[i]; j <= amount; j++) {              //正序遍历背包(金额)-- 表示可重复使用硬币:注意,这里从coins[i]开始遍历,因为如果金额小于当前硬币的面值,那么当前硬币无法使用(保证j - coins[i]大于0)if (dp[j - coins[i]] != INT_MAX) {      //说明存在一种或多种方式可以组成金额 j - coins[i] ,这时再加上一个当前硬币 coins[i],就可以组成金额 j -- 间接性说明此时可以凑成总金额dp[j] = min(dp[j - coins[i]] + 1, dp[j]);       //不断更新凑成金额 j 所需的最少的硬币个数}}}if (dp[amount] == INT_MAX) {      //没有任何一种硬币组合能组成总金额amountreturn -1;}else    return dp[amount];}
};

题目二: 279.完全平方数

题目链接

279. 完全平方数 - 力扣(LeetCode)

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,149 和 16 都是完全平方数,而 3 和 11 不是。

示例 1:

输入:n = 12输出:3 解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13输出:2解释:13 = 4 + 9
 

提示:

  • 1 <= n <= 104
题解:动态规划--完全背包

这道题和上一道零钱兑换思路上基本一致,需要注意的就是如何实现完全平方数的列举。

这里先看看我的代码:

 直接新建一个数组,存放每个数字的平方即可。-- 显然,这样时间复杂度和空间复杂度都加大了。

我们可以直接在遍历物品与背包的过程中实现对完全平方数的操作。

如下是修改后的代码:

class Solution {
public:int numSquares(int n) {/* 完全背包问题--一维dp */vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i * i <= n; i++) {             //先遍历物品再遍历背包for (int j = i * i; j <= n; j++) {      //正序遍历背包--这里的for循环直接实现了j为完全平方数dp[j] = min(dp[j - i * i] + 1, dp[j]);}}return dp[n];}
};

题目三:139.单词拆分

题目链接

139. 单词拆分 - 力扣(LeetCode)

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同
题解:动态规划--完全背包

这道题实际上的意思就是判断是否能从字典中选择单词构成字符串s -- 需要注意的就是每个单词可以重复使用,而为了构成字符串,一定是讲求顺序的 -- 这就容易联想到完全背包的排列数问题

在这里,就应该定义bool类型的dp数组,dp[i]表示字符串s的前i个字符是否可以被拆分成若干个字典(wordDict)中出现的单词。

初始化整个 dp 数组为 false,而 dp[0] = true。

排列数问题--先背包再物品,这里用到了str()函数,用于截取字符串的子串部分(这里需要注意子串部分的长度),判断是否有某个单词与之匹配。

代码如下:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size() + 1, false);          //定义bool类型的dp数组,dp[i]表示字符串s的前i个字符是否可以被拆分成若干个字典(wordDict)中出现的单词dp[0] = true;       //初始化dp[0] = 0/*  排列数问题--先背包再物品  */for(int i = 1; i <= s.size(); i++) {            //正序遍历字符串s(背包)    for(auto word: wordDict) {          //遍历单词(物品):这样写更直观int size = word.size();    //记录当前单词长度(背包问题中的物品体积)   if ((i - size) >= 0 && s.substr(i - size, size) == word) {        //从s中提取的子字符串s.str(i - size, size)和字典中当前单词 word 匹配时--注意这里需要保证(i - size) >= 0即str(start, len)提取子串的初始位置start不能为负dp[i] = dp[i] || dp[i - size];       //表示如果 dp[i - size] 为真,则 dp[i] 也应为真 }}       }return dp[s.size()];        //整个字符串进行判断}   
};

三、小结

今天的打卡到此也就结束了,完全背包问题暂时也就告一段落,后边会继续加油!


http://www.ppmy.cn/news/1516959.html

相关文章

云轴科技ZStack AIOS平台智塔亮相FDS金融领袖峰会

人工智能&#xff08;AI&#xff09;正以前所未有的速度渗透到金融系统&#xff0c;推动着金融服务的创新和变革。这种深度融合不仅可以提高金融服务的效率和准确性&#xff0c;未来还可催生全新的金融产品和服务模式。尤其是生成式人工智能&#xff08;GenAI&#xff09;的出现…

系统分析师5-数据库特训专题

文章目录 1 数据库设计概述2 规范化与反规范化2.1 规范化2.2 反规范化2.3 案例分析例题1 3 数据库索引与视图的应用3.1 数据库索引3.2 数据库视图3.3 案例分析例题2 4 分布式数据库系统5 数据库分区分表分库5.1 案例分析例题3 6 分布式事务增补6.1 案例分析例题4 7 NoSQL8 附录…

redis实战——go-redis的使用与redis基础数据类型的使用场景(二)

一.go-redis操作hash 常用命令&#xff1a; redisClient.HSet("map", "name", "jack") // 批量设置 redisClient.HMSet("map", map[string]interface{}{"a": "b", "c": "d", "e"…

如何使用ssm实现基于SSM的旅游管理系统

TOC ssm285基于SSM的旅游管理系统jsp 第1章 绪论 1.1 课题背景 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。所以各行业&…

三级_网络技术_50_综合题(报文)

一、 下图是校园网某台主机在命令行模式执行某个命令时用wireshark捕获的数据包 请根据图中信息回答下列问题。 (1)该主机上执行的命令是__________ (2)该主机上使用的DNS服务器的IP地址是__________ (3)该主机的IP地址是__________ 该主机的MAC地址是__________ (4)主机…

网络安全的历史

如今&#xff0c;网络安全几乎成为各大公司和利益相关者关注的焦点。但在早期&#xff0c;网络安全的概念非常模糊。 直到多年以后&#xff0c;由于网络攻击和危险实体威胁的频繁发生&#xff0c;网络安全的发展才受到重视。这些措施的发展成为了网络安全的演变。 网络安全起…

Nginx 负载均衡详解

一、Nginx 简介 Nginx 是一个高性能的开源 Web 服务器和反向代理服务器&#xff0c;以其轻量级、高并发、低内存消耗等特点著称。Nginx 不仅适用于静态资源的快速分发&#xff0c;还广泛应用于负载均衡、反向代理等场景。通过Nginx&#xff0c;可以轻松地构建一个高效、可靠且…

8月27复盘日记

8月27复盘日记 前言今日感恩今日知识今日反思今日名言 前言 今天早上是七点半起床嘻嘻&#xff0c;昨晚和舍友聊天&#xff0c;分享小时候的趣事&#xff0c;以及一些观点&#xff0c;聊得有些激动&#xff0c;就比较难以入睡   今天天气又是超级让人幸福&#xff01;&#x…