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

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

目录

一、做题心得

二、题目与题解

题目一: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()];        //整个字符串进行判断}   
};

三、小结

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

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



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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

第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 ;