day38|leetcode 322零钱兑换,279.完全平方数,139.单词拆分

322. 零钱兑换

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

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

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

这题与零钱兑换II的区别在于本题需要返回最小数

动规五部曲:

(1)dp数组的含义:dp[j]代表凑成总金额为j所需的最少的硬币个数

(2)确定递推公式:dp[j-coins[i]]就是凑成j-coins[i]所需的最少的硬币个数,加上coins[i]就是dp[j]即dp[j-coins[i]]+1,由于求的是最小值,所以dp[j]=min(dp[j-coins]+1,dp[j]);

(3)初始化:dp[0]=0,由递推公式可知为了防止0覆盖之后的所有元素,除了dp[0]其他位置都应该初始化为非零数

(4)确定遍历顺序:由于求的是最小值,所以并不需要考虑组合数还是排列数

(5)打印dp数组

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int bagweight = amount;
        vector<int>dp(bagweight+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++)//先遍历物品
        {
            for(int j=coins[i];j<=bagweight;j++)
            {
                if(dp[j-coins[i]]!=INT_MAX)//如果等于初始值就跳过
                   dp[j]=min(dp[j-coins[i]]+1,dp[j]);
            }
        }
        if(dp[bagweight]==INT_MAX)return -1;
        return dp[bagweight];
    }
};

279. 完全平方数

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

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

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

题目分析:背包容量就是n,完全平方数就是物品

完全平方数就是i*i

动规五部曲:

(1)dp[j]含义:和为j的完全平方数的最少数量

(2)确定递推公式:dp[j]=min(dp[j-i*i]+1,dp[j]);

(3)初始化:dp[0]=0,为了防止后续的值被覆盖,除了dp[0]其他都应该初始化为INT_MAX

(4)确定遍历顺序:求最小值不强调组合数还是排列数

(5)打印dp数组

class Solution {
public:
    int numSquares(int n) {
        int bagweight = n;
        vector<int>dp(bagweight+1,INT_MAX);
        dp[0]=0;
        for(int j=0;j<=n;j++)//先遍历背包
        {
            for(int i=1;i*i<=j;i++)
            {
                dp[j]=min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[bagweight];
    }
};

139. 单词拆分

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

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

示例 1:

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

题意分析:字符串是s,单词是物品

动规五部曲:

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

(2)确定递推公式:如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

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

(3)初始化:由递推公式可知,dp[0]决定了后续的,所以dp[0]=true,其他设为false

(4)确定遍历顺序:先遍历背包后遍历物品,因为s="apple pen apple" 时s=apple+pen+apple,其他顺序不是s,所以强调顺序,也就是属于排列数

(5)打印dp数组

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
      unordered_set<string>wordSet(wordDict.begin(),wordDict.end());
      vector<bool>dp(s.size()+1,false);
      dp[0]=true;
      for(int j=1;j<=s.size();j++)//先遍历背包
      {
        for(int i=0;i<j;i++)//再遍历物品
        {
            string str = s.substr(i,j-i);
            if(wordSet.find(str)!=wordSet.end() && dp[i])
            {
                dp[j]=true;
            }
        }
      }
      return dp[s.size()];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/964471.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【力扣】53.最大子数组和

AC截图 题目 思路 这道题主要考虑的就是要排除负数带来的负面影响。如果遍历数组&#xff0c;那么应该有如下关系式&#xff1a; currentAns max(prenums[i],nums[i]) pre是之前记录的最大和&#xff0c;如果prenums[i]小于nums[i]&#xff0c;就要考虑舍弃pre&#xff0c;从…

本地部署DeepSeek教程(Mac版本)

第一步、下载 Ollama 官网地址&#xff1a;Ollama 点击 Download 下载 我这里是 macOS 环境 以 macOS 环境为主 下载完成后是一个压缩包&#xff0c;双击解压之后移到应用程序&#xff1a; 打开后会提示你到命令行中运行一下命令&#xff0c;附上截图&#xff1a; 若遇…

代码随想录算法【Day36】

Day36 1049. 最后一块石头的重量 II 思路 把石头尽可能分成两堆&#xff0c;这两堆重量如果相似&#xff0c;相撞后所剩的值就是最小值 若石头的总质量为sum&#xff0c;可以将问题转化为0-1背包问题&#xff0c;即给一个容量为sum/2的容器&#xff0c;如何尽量去凑满这个容…

【Numpy核心编程攻略:Python数据处理、分析详解与科学计算】2.28 NumPy+Matplotlib:科学可视化的核心引擎

2.28 NumPyMatplotlib&#xff1a;科学可视化的核心引擎 目录 #mermaid-svg-KTB8Uqiv5DLVJx7r {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-KTB8Uqiv5DLVJx7r .error-icon{fill:#552222;}#mermaid-svg-KTB8Uqiv5…

基序和纯度分数的计算

以下对这两个概念的详细解释&#xff1a; 基序 纯度分数 PWM矩阵的来源 为什么会有PWM矩阵&#xff1f; 一个特定的转录因子&#xff08;TF&#xff09;的结合位点的基序&#xff08;motif&#xff09;并不是唯一的。实际上&#xff0c;TF结合位点通常具有一定的序列变异性&a…

Linux下的编辑器 —— vim

目录 1.什么是vim 2.vim的模式 认识常用的三种模式 三种模式之间的切换 命令模式和插入模式的转化 命令模式和底行模式的转化 插入模式和底行模式的转化 3.命令模式下的命令集 光标移动相关的命令 复制粘贴相关命令 撤销删除相关命令 查找相关命令 批量化注释和去…

有用的sql链接

『SQL』常考面试题&#xff08;2——窗口函数&#xff09;_sql的窗口函数面试题-CSDN博客 史上最强sql计算用户次日留存率详解&#xff08;通用版&#xff09;及相关常用函数 -2020.06.10 - 知乎 (zhihu.com) 1280. 学生们参加各科测试的次数 - 力扣&#xff08;LeetCode&…

算法题(57):找出字符串中第一个匹配项的下标

审题: 需要我们根据原串与模式串相比较并找到完全匹配时子串的第一个元素索引&#xff0c;若没有则返回-1 思路&#xff1a; 方法一&#xff1a;BF暴力算法 思路很简单&#xff0c;我们用p1表示原串的索引&#xff0c;p2表示模式串索引。遍历原串&#xff0c;每次遍历都匹配一次…

线性回归原理和算法

线性回归可以说是机器学习中最基本的问题类型了&#xff0c;这里就对线性回归的原理和算法做一个小结。 对于线性回归的损失函数&#xff0c;我们常用的有两种方法来求损失函数最小化时候的θ参数&#xff1a;一种是梯度下降&#xff0c;一种是最小二乘法。 为了防止模型的过拟…

npm知识

npm 是什么 npm 为你和你的团队打开了连接整个 JavaScript 天才世界的一扇大门。它是世界上最大的软件注册表&#xff0c;每星期大约有 30 亿次的下载量&#xff0c;包含超过 600000 个包&#xff08;package&#xff09;&#xff08;即&#xff0c;代码模块&#xff09;。来自…

【贪心算法篇】:“贪心”之旅--算法练习题中的智慧与策略(三)

✨感谢您阅读本篇文章&#xff0c;文章内容是个人学习笔记的整理&#xff0c;如果哪里有误的话还请您指正噢✨ ✨ 个人主页&#xff1a;余辉zmh–CSDN博客 ✨ 文章所属专栏&#xff1a;贪心算法篇–CSDN博客 文章目录 前言例题1.最优除法2.跳跃游戏23.跳跃游戏14.加油站5.单调递…

什么是物理地址,什么是虚拟地址?

摘要 什么是物理地址&#xff0c;什么是虚拟地址&#xff1f; 如果处理器没有MMU或未启用&#xff0c;CPU执行单元发出的内存地址直接传到芯片引脚上&#xff0c;被内存芯片接受&#xff0c;这称为物理地址&#xff08;Physical Addraress&#xff09; 如果处理器启用了MMU&a…

LabVIEW图片识别逆向建模系统

本文介绍了一个基于LabVIEW的图片识别逆向建模系统的开发过程。系统利用LabVIEW的强大视觉处理功能&#xff0c;通过二维图片快速生成对应的三维模型&#xff0c;不仅降低了逆向建模的技术门槛&#xff0c;还大幅提升了建模效率。 ​ 项目背景 在传统的逆向建模过程中&#xf…

小程序的协同工作与发布

1.小程序API的三大分类 2.小程序管理的概念&#xff0c;以及成员管理两个方面 3.开发者权限说明以及如何维护项目成员 4.小程序版本

Unity 粒子特效在UI中使用裁剪效果

1.使用Sprite Mask 首先建立一个粒子特效在UI中显示 新建一个在场景下新建一个空物体&#xff0c;添加Sprite Mask组件&#xff0c;将其的Layer设置为UI相机渲染的UI层&#xff0c; 并将其添加到Canvas子物体中&#xff0c;调整好大小&#xff0c;并选择合适的Sprite&#xff…

Java设计模式:行为型模式→状态模式

Java 状态模式详解 1. 定义 状态模式&#xff08;State Pattern&#xff09;是一种行为型设计模式&#xff0c;它允许对象在内部状态改变时改变其行为。状态模式通过将状态需要的行为封装在不同的状态类中&#xff0c;实现对象行为的动态改变。该模式的核心思想是分离不同状态…

中间件的概念及基本使用

什么是中间件 中间件是ASP.NET Core的核心组件&#xff0c;MVC框架、响应缓存、身份验证、CORS、Swagger等都是内置中间件。 广义上来讲&#xff1a;Tomcat、WebLogic、Redis、IIS&#xff1b;狭义上来讲&#xff0c;ASP.NET Core中的中间件指ASP.NET Core中的一个组件。中间件…

泰山派Linux环境下自动烧录脚本(EMMC 2+16G)

脚本名字&#xff1a; download.sh 输入./download -h获取帮助信息 &#xff0c;其中各个IMG/TXT烧录的地址和路径都在前几行修改即可 #!/bin/bash# # DownLoad.sh 多镜像烧录脚本 # 版本&#xff1a;1.1 # 作者&#xff1a;zhangqi # 功能&#xff1a;通过参数选择烧录指定镜…

使用开源项目:pdf2docx,让PDF转换为Word

目录 1.安装python 2.安装 pdf2docx 3.使用 pdf2docx 转换 PDF 到 Word pdf2docx&#xff1a;GitCode - 全球开发者的开源社区,开源代码托管平台 环境&#xff1a;windows电脑 1.安装python Download Python | Python.org 最好下载3.8以上的版本 安装时记得选择上&#…

一、TensorFlow的建模流程

1. 数据准备与预处理&#xff1a; 加载数据&#xff1a;使用内置数据集或自定义数据。 预处理&#xff1a;归一化、调整维度、数据增强。 划分数据集&#xff1a;训练集、验证集、测试集。 转换为Dataset对象&#xff1a;利用tf.data优化数据流水线。 import tensorflow a…