当前位置: 首页 > news >正文

LeetCode算法题解(动态规划)|LeetCode322. 零钱兑换、LeetCode279. 完全平方数

一、LeetCode322. 零钱兑换

题目链接:322. 零钱兑换
题目描述:

给你一个整数数组 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[j],dp[j-coins[i]]+1),现有硬币coins[i],那么凑成金额为j所需的最少硬币数可有凑成金额为j-coins[i]所需最少硬币数推出。

初始化:

因为要求的是最少硬币数,所以除dp[0]初始化成0之外,其他所有情况都要初始化成最大值。

遍历顺序:

先遍历不同面额的硬币,在遍历总金额。

打印dp数组进行验证。

代码如下:

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];for(int i = 1; i < amount + 1; i++) dp[i] = Integer.MAX_VALUE;dp[0] = 0;//除了dp[0]其他都初始化成最大值for(int i = 0; i < coins.length; i++) {//遍历每种硬币for(int j = coins[i]; j <= amount; j++) {//遍历总金额if(dp[j - coins[i]] != Integer.MAX_VALUE) {//注意如果dp[j-coins[i]]是个最大int类型整数的话,dp[j-coins[i]]+1会溢出,变成负数,从而影响比较结果,所以只有它不是初始最大值是,才有选择的必要。dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);}}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

二、LeetCode279. 完全平方数

题目链接:279. 完全平方数
题目描述:

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

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

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= n <= 104
算法分析:

因为每个完全平方数可以无限取,所以这也是一道完全背包问题。

定义dp数组及下标含义:

dp[j]表示组成和为j的完全平方数最少数量。

递推公式:

dp[j]=min(dp[j],dp[j-i*i]+1),现有完全平方数i*i,那么组成j的最少完全平方数数量可有dp[j-i*i]推导而出,也即组成j-i*i的最少完全平方数数量加上现在这个完全平方数(i*i)。

初始化:

因为要求的是完全平方数最少数量,所以除dp[0]初始化成0外,其他所有情况都要初始化成最大值。

遍历顺序:

先遍历小于等于目标和n的每个完全平方数,在遍历总和。

打印dp数组进行验证。

代码如下:

class Solution {public int numSquares(int n) {int[] dp = new int[n + 1];//除dp[0]意外,其他所有情况都初始化成最大值dp[0] = 0;for(int i = 1; i <= n; i++)dp[i] = Integer.MAX_VALUE;for(int i = 1; i * i <= n; i++) {//遍历每个完全平方数for(int j = i * i; j <= n; j++) {//遍历总和dp[j] = Math.min(dp[j],dp[j-i * i] + 1);}}return dp[n];}
}

总结

这两道题都是完全背包问题中,求最少元素个数的情况。

相关文章:

LeetCode算法题解(动态规划)|LeetCode322. 零钱兑换、LeetCode279. 完全平方数

一、LeetCode322. 零钱兑换 题目链接&#xff1a;322. 零钱兑换 题目描述&#xff1a; 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一…...

Python Web开发基础知识篇

一&#xff0c;基础知识篇 本片文章会简单地说一些python开发web中所必须的一些基础知识。主要包括HTML和css基础、JavaScript基础、网络编程基础、MySQL数据库基础、Web框架基础等知识。 1,Web简介 Web&#xff0c;全称为World Wide Web&#xff0c;也就是WWW&#xff0c;万…...

企业计算机服务器中了360勒索病毒怎么办,360勒索病毒解密文件恢复

计算机技术的不断发展&#xff0c;为企业的生产运营提供了极大便利&#xff0c;不仅提升了办公效率&#xff0c;还促进了企业的发展。企业计算机在日常工作中一定加以防护&#xff0c;减少网络威胁事件的产生&#xff0c;确保企业的生产生产运营。最近&#xff0c;网络上的360后…...

LeetCode无重复字符的最长字符串的Java实现

题目 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长连续子字符串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子字符串是 "abc"&#xff0c;所以其长度为 3。示例 2: 输入: s "bbbbb" 输…...

opencv-图像平滑

高斯平滑 高斯平滑即采用高斯卷积核对图像矩阵进行卷积操作。高斯卷积核是一个近似服从高斯分布的矩阵&#xff0c;随着距离中心点的距离增加&#xff0c;其值变小。这样进行平滑处理时&#xff0c;图像矩阵中锚点处像素值权重大&#xff0c;边缘处像素值权重小。 import cv2 …...

【开源】基于Vue.js的天然气工程运维系统的设计和实现

项目编号&#xff1a; S 022 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S022&#xff0c;文末获取源码。} 项目编号&#xff1a;S022&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统角色分类2.2 核心功能2.2.1 流程…...

数据丢失抢救神器之TOP10 Android 数据恢复榜单

在快节奏的数字时代&#xff0c;我们的生活越来越与智能手机交织在一起&#xff0c;使它们成为重要数据和珍贵记忆的存储库。由于意外删除、软件故障或硬件故障而丢失数据可能是一种痛苦的经历。值得庆幸的是&#xff0c;技术领域提供了 Android 数据恢复软件形式的解决方案。这…...

梨花声音教育,动作电影中配音也能带来听见“冲击力”

在为动作电影提供配音服务时&#xff0c;配音员家需要通过声音的力量来增强画面上的动作张力、传递角色的活力&#xff0c;以及呈现出电影中的紧迫感。动作片充斥着快节奏的场景交替、紧张的格斗和惊险的逃逸等元素&#xff0c;配音需要精确、生动且充满动力。为动作电影配音应…...

Elaticsearch学习

Elaticsearch 索引 1、索引创建 PUT /index_v1 {"settings": {"number_of_shards": 3,"number_of_replicas": 1},"mappings": {"properties": {"aaa": {"type": "keyword","store&qu…...

【腾讯云云上实验室】向量数据库+LangChain+LLM搭建智慧辅导系统实践

目录 一、搭建智慧辅导系统——向量数据库实践指南1.1、创建向量数据库并新建集合1.2、使用 TKE 快速部署 ChatGLM1.3、部署 LangChain PyPDFVectorDB等组件1.4、配置知识库语料1.5、基于 VectorDB LLM 的智能辅导助手 二、LLM时代的次世代引擎——向量数据库2.1、向量数据库L…...

从0开始学习JavaScript--深入了解JavaScript框架

JavaScript框架在现代Web开发中扮演着关键角色&#xff0c;为开发者提供了丰富的工具和抽象层&#xff0c;使得构建复杂的、高性能的Web应用变得更加容易。本文将深入探讨JavaScript框架的核心概念、常见框架的特点以及它们在实际应用中的使用。 JavaScript框架的作用 JavaSc…...

【教3妹学编程-算法题】二叉树中的伪回文路径

3妹&#xff1a;好冷啊&#xff0c; 冻得瑟瑟发抖啦 2哥 : 又一波寒潮来袭&#xff0c; 外面风吹的呼呼的。 3妹&#xff1a;今天还有雨&#xff0c;2哥上班记得带伞。 2哥 : 好的 3妹&#xff1a;哼&#xff0c;不喜欢冬天&#xff0c;也不喜欢下雨天&#xff0c;要是我会咒语…...

快速上手Banana Pi BPI-M4 Zero 全志科技H618开源硬件开发开发板

Linux[编辑] 准备[编辑] 1. Linux镜像支持SD卡或EMMC启动&#xff0c;并且会优先从SD卡启动。 2. 建议使用A1级卡&#xff0c;至少8GB。 3. 如果您想从 SD 卡启动&#xff0c;请确保可启动 EMMC 已格式化。 4. 如果您想从 EMMC 启动并使用 Sdcard 作为存储&#xff0c;请确…...

Node.js入门指南(三)

目录 Node.js 模块化 介绍 模块暴露数据 导入模块 导入模块的基本流程 CommonJS 规范 包管理工具 介绍 npm cnpm yarn nvm的使用 我们上一篇文章介绍了Node.js中的http模块&#xff0c;这篇文章主要介绍Node.js的模块化&#xff0c;包管理工具以及nvm的使用。 Node…...

Leetcode—2824.统计和小于目标的下标对数目【简单】

2023每日刷题&#xff08;三十九&#xff09; Leetcode—2824.统计和小于目标的下标对数目 实现代码 class Solution { public:int countPairs(vector<int>& nums, int target) {int n nums.size();sort(nums.begin(), nums.end());int left 0, right left 1;i…...

【基础架构】part-2 可扩展性

文章目录 可扩展性&#xff08;Scalability&#xff09;2.1 水平扩展2.2 垂直扩展2.3 弹性扩展 三、可靠性&#xff08;Reliability&#xff09;3.1 容错机制3.2 错误处理和恢复策略3.3 监控和自动化运维 四、 安全性&#xff08;Security&#xff09;4.1 身份验证和授权4.2 加…...

[SWPUCTF 2021 新生赛]no_wakeup

直接赋值即可 $a ->admin admin; $a ->passwd wllm; 发现没有绕过&#xff0c;改成大于2的绕过__wakeup 这是因为PHP在反序列化时会检查序列化字符串的长度&#xff0c;如果长度小于等于2&#xff0c;则不会调用__wakeup()方法。...

类和对象(3)日期类的实现

日期类的实现 一&#xff0c;声明二&#xff0c;函数成员定义2.1构造函数2.2获取月份天数2.3比较运算符2.3.1等于和大于2.3.2其他 2.4计算运算符2.4.1 &&2.4.2-&&- 2.5日期-日期 一&#xff0c;声明 class Date { public:Date(int year 1, int month 1, int…...

分布式篇---第五篇

系列文章目录 文章目录 系列文章目录前言一、你知道哪些限流算法?二、说说什么是计数器(固定窗口)算法三、说说什么是滑动窗口算法前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去…...

SpringMVC(二)

八、HttpMessageConverter HttpMessageConverter&#xff0c;报文信息转换器&#xff0c;将请求报文转换为Java对象&#xff0c;或将Java对象转换为响应报文 HttpMessageConverter提供了两个注解和两个类型&#xff1a;RequestBody&#xff0c;ResponseBody&#xff0c;Reque…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...