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

leetcode 刷题day36动态规划Part05 背包问题(完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯 (进阶))

完全背包

完全背包的每件商品都有无限个,和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次,01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的,所以要从小到大去遍历。

518. 零钱兑换 II

思路:每一种面额的硬币有无限个是完全背包问题。背包的容量为amount,物品的重量和价值都是硬笔金额。求组合数,
dp[j]表示容量为j时成立的组合数。

代码如下:

class Solution {public int change(int amount, int[] coins) {int[] dp=new int[amount+1];dp[0]=1;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}

377. 组合总和 Ⅳ

思路:本题与上一题的区别在于本题是求排列的个数。

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

代码如下:

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp=new int[target+1];dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<nums.length;i++){if(j>=nums[i]){dp[j]+=dp[j-nums[i]];}}}return dp[target];}
}

70. 爬楼梯 (进阶)

思路:dp[i]指爬到有i个台阶的楼顶,有dp[i]种方法。台阶可以重复使用-完全背包问题,从前往后遍历背包。求排列的个数,背包是外层循环。

代码如下:

import java.util.Scanner;
class Main{public static void main(String [] args){Scanner scan=new Scanner(System.in);int m,n;while (scan.hasNextInt()) {n=scan.nextInt();m=scan.nextInt();int[] dp=new int[n+1];dp[0]=1;for(int j=1;j<=n;j++){for(int i=1;i<=m;i++){if(j>=i) dp[j]+=dp[j-i];}}System.out.println(dp[n]);}}
}

相关文章:

leetcode 刷题day36动态规划Part05 背包问题(完全背包、518. 零钱兑换 II、377. 组合总和 Ⅳ、70. 爬楼梯 (进阶))

完全背包 完全背包的每件商品都有无限个&#xff0c;和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次&#xff0c;01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的&#xff0c;所以要从小到大去遍历。 518. 零钱兑换 II 思路&#…...

检查jar冲突,查找存在相同class的jar

写在前面 本文看下如何查找jar冲突&#xff0c;即查找哪些jar包中存在相同的class。如果是存在相同jar的不同版本&#xff0c;基本一眼就能看出来&#xff0c;然后结合maven的依赖关系将其剔除掉即可&#xff0c;但是当你遇到了有人手动拷贝某些class到jar包中导致冲突的情况时…...

PhpStudy-PHP5.4.45后门漏洞应用程序(C++/base64/winhttp)

PhpStudy-PHP5.4.45后门漏洞应用程序&#xff08;C/base64/winhttp&#xff09; 前言引言&#xff08;时间回到多年前&#xff09; PhpShellCmd.exe使用介绍&#xff1a;&#xff08;1&#xff09;输入网址检测是否存在PHP/5.4.45&#xff08;2&#xff09;whoami&#xff08;3…...

【优选算法】(第二十七篇)

目录 重排链表&#xff08;medium&#xff09; 题目解析 讲解算法原理 编写代码 合并K个升序链表&#xff08;hard&#xff09; 题目解析 讲解算法原理 编写代码 重排链表&#xff08;medium&#xff09; 题目解析 1.题目链接&#xff1a;. - 力扣&#xff08;LeetCod…...

学习Flask框架

Flask简介 Flask是一个使用 Python 编写的轻量级 Web 应用框架。其 WSGI 工具箱采用 Werkzeug &#xff0c;模板引擎则使用 Jinja2 。Flask使用 BSD 授权。 Flask也被称为 “microframework” &#xff0c;因为它使用简单的核心&#xff0c;用 extension 增加其他功能。Flask没…...

Elasticsearch:使用 LLM 实现传统搜索自动化

作者&#xff1a;来自 Elastic Han Xiang Choong 这篇简短的文章是关于将结构化数据上传到 Elastic 索引&#xff0c;然后将纯英语查询转换为查询 DSL 语句&#xff0c;以使用特定过滤器和范围搜索特定条件。完整代码位于此 Github repo 中。 首先&#xff0c;运行以下命令安装…...

人脸表情行为识别系统源码分享

人脸表情行为识别系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…...

ThreadLocal原理解析及面试

基本使用 讲原理之前&#xff0c;我简单写个demo小程序说说怎么使用 public class TestThreadLocal {public static void main(String[] args) throws InterruptedException {ThreadLocal<String> tl new ThreadLocal();/**主线程设置了一个值*/tl.set("SSSSSs&…...

探索未来:mosquitto-python,AI领域的新宠

文章目录 探索未来&#xff1a;mosquitto-python&#xff0c;AI领域的新宠背景&#xff1a;为何选择mosquitto-python&#xff1f;库简介&#xff1a;mosquitto-python是什么&#xff1f;安装指南&#xff1a;如何安装mosquitto-python&#xff1f;函数用法&#xff1a;5个简单…...

C++版iwanna1

第一篇目录 开头程序Game.cpp源文件Player.h头文件Player.cpp源文件trigger.h头文件trigger.cpp源文件Cmp.h头文件Cmp.cpp源文件 开头 大家好&#xff0c;我叫这是我58。 程序 Game.cpp源文件 #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <c…...

LSTM变种模型

一、GRU 1.概念 GRU&#xff08;门控循环单元&#xff0c;Gated Recurrent Unit&#xff09;是一种循环神经网络&#xff08;RNN&#xff09;的变体&#xff0c;旨在解决标准 RNN 在处理长期依赖关系时遇到的梯度消失问题。GRU 通过引入门控机制简化了 LSTM&#xff08;长短期…...

Python进阶--函数进阶

目录 1. 函数多返回值 2. 函数多种传参方式 (1). 位置参数 (2). 关键字参数 (3). 缺省参数 (4). 不定长参数 3. 匿名函数 (1). 函数作为参数传递 (2). lambda匿名函数 1. 函数多返回值 def return_num():return 1# 返回1之后就不会再向下继续执行函数体return 2 resu…...

elasticsearch 8.2 设置账号密码

背景:单节点集群数据写入测试-CSDN博客 前述项目支持设置账号密码,但8+版本似乎不能那么做了。 ERROR: [1] bootstrap checks failed. You must address the points described in the following [1] lines before starting Elasticsearch. bootstrap check failure [1] of…...

JavaScript代码如何测试?

测试JavaScript代码是确保其功能、性能和可靠性的关键步骤。以下是一些详细的步骤和方法&#xff0c;用于测试JavaScript代码&#xff1a; 1、编写测试用例 首先&#xff0c;你需要为要测试的JavaScript代码编写测试用例。这些用例应该涵盖代码的各种功能和场景&#xff0c;包…...

案例分享—国外ui设计优秀案例

国外企业更注重用户体验设计&#xff0c;倾向于简洁清晰的设计风格&#xff0c;以提高用户的使用体验和操作效率。他们注重“简约至上”的设计理念&#xff0c;认为简洁的设计可以减少用户的认知负担&#xff0c;提高用户的工作效率。 设计师在界面设计中往往更加注重创意性和个…...

在JavaScript中,改变this指向的call,apply,bind有什么区别,原理分别是什么?

在JavaScript中&#xff0c;call、apply和bind方法都是用来改变函数执行时this指向的。 以下通过一个Demo帮助理解&#xff0c;代码如下&#xff1a; var obj {name: lisi,sayHello: function() {console.log(this.name)} } obj.sayHello()// lisifunction sayHello() {conso…...

Redis 缓存策略详解:提升性能的四种常见模式

在现代分布式系统中&#xff0c;缓存是提升性能和减轻数据库负载的关键组件。Redis 作为一种高性能的内存数据库&#xff0c;被广泛应用于缓存层。本文将深入探讨几种常用的 Redis 缓存策略&#xff0c;包括旁路缓存模式&#xff08;Cache-Aside Pattern&#xff09;、读穿透模…...

怎么建设网站吸引并留住客户

如何建设网站吸引并留住客户 在当今数字化时代&#xff0c;网站是企业与客户沟通的重要桥梁。一个设计精良、功能完备的网站不仅能吸引客户的注意&#xff0c;还能有效留住他们。以下是一些建设网站的关键策略。 **1. 用户体验优先** 网站的整体用户体验&#xff08;UX&#x…...

培训行业为什么要搭建自己的知识付费小程序平台?集师知识付费系统 集师知识付费小程序 集师知识服务系统 集师线上培训系统 集师线上卖课小程序

在当今这个信息爆炸的时代&#xff0c;培训行业正面临前所未有的变革与挑战。传统的线下授课模式虽然经典&#xff0c;但在互联网技术的冲击下&#xff0c;其局限性日益凸显。为了更好地适应市场需求&#xff0c;提升服务效率与用户体验&#xff0c;培训行业亟需搭建自己的知识…...

Linux:Linux进程概念

✨✨✨学习的道路很枯燥&#xff0c;希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一 冯诺依曼体系结构 二 操作系统(Operator System&#xff09; 2.1 概念 2.2 设计OS的目的 ​编辑 2.3 OS如何进行管理 ​编辑2.4 总结 三 进程的标示符 3.1 基本概念…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器

一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下&#xff0c;音视频内容犹如璀璨繁星&#xff0c;点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频&#xff0c;到在线课堂中知识渊博的专家授课&#xff0c;再到影视平台上扣人心弦的高清大片&#xff0c;音…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...