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. 爬楼梯 (进阶))
完全背包 完全背包的每件商品都有无限个,和01背包的一不同主要体现在遍历顺序上。为了保证每个物品仅被添加一次,01背包内嵌的循环是从大到小遍历。而完全背包的物品是可以添加多次的,所以要从小到大去遍历。 518. 零钱兑换 II 思路&#…...
检查jar冲突,查找存在相同class的jar
写在前面 本文看下如何查找jar冲突,即查找哪些jar包中存在相同的class。如果是存在相同jar的不同版本,基本一眼就能看出来,然后结合maven的依赖关系将其剔除掉即可,但是当你遇到了有人手动拷贝某些class到jar包中导致冲突的情况时…...
PhpStudy-PHP5.4.45后门漏洞应用程序(C++/base64/winhttp)
PhpStudy-PHP5.4.45后门漏洞应用程序(C/base64/winhttp) 前言引言(时间回到多年前) PhpShellCmd.exe使用介绍:(1)输入网址检测是否存在PHP/5.4.45(2)whoami(3…...
【优选算法】(第二十七篇)
目录 重排链表(medium) 题目解析 讲解算法原理 编写代码 合并K个升序链表(hard) 题目解析 讲解算法原理 编写代码 重排链表(medium) 题目解析 1.题目链接:. - 力扣(LeetCod…...
学习Flask框架
Flask简介 Flask是一个使用 Python 编写的轻量级 Web 应用框架。其 WSGI 工具箱采用 Werkzeug ,模板引擎则使用 Jinja2 。Flask使用 BSD 授权。 Flask也被称为 “microframework” ,因为它使用简单的核心,用 extension 增加其他功能。Flask没…...
Elasticsearch:使用 LLM 实现传统搜索自动化
作者:来自 Elastic Han Xiang Choong 这篇简短的文章是关于将结构化数据上传到 Elastic 索引,然后将纯英语查询转换为查询 DSL 语句,以使用特定过滤器和范围搜索特定条件。完整代码位于此 Github repo 中。 首先,运行以下命令安装…...
人脸表情行为识别系统源码分享
人脸表情行为识别系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…...
ThreadLocal原理解析及面试
基本使用 讲原理之前,我简单写个demo小程序说说怎么使用 public class TestThreadLocal {public static void main(String[] args) throws InterruptedException {ThreadLocal<String> tl new ThreadLocal();/**主线程设置了一个值*/tl.set("SSSSSs&…...
探索未来:mosquitto-python,AI领域的新宠
文章目录 探索未来:mosquitto-python,AI领域的新宠背景:为何选择mosquitto-python?库简介:mosquitto-python是什么?安装指南:如何安装mosquitto-python?函数用法:5个简单…...
C++版iwanna1
第一篇目录 开头程序Game.cpp源文件Player.h头文件Player.cpp源文件trigger.h头文件trigger.cpp源文件Cmp.h头文件Cmp.cpp源文件 开头 大家好,我叫这是我58。 程序 Game.cpp源文件 #define _CRT_SECURE_NO_WARNINGS 1 #include <iostream> #include <c…...
LSTM变种模型
一、GRU 1.概念 GRU(门控循环单元,Gated Recurrent Unit)是一种循环神经网络(RNN)的变体,旨在解决标准 RNN 在处理长期依赖关系时遇到的梯度消失问题。GRU 通过引入门控机制简化了 LSTM(长短期…...
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代码是确保其功能、性能和可靠性的关键步骤。以下是一些详细的步骤和方法,用于测试JavaScript代码: 1、编写测试用例 首先,你需要为要测试的JavaScript代码编写测试用例。这些用例应该涵盖代码的各种功能和场景,包…...
案例分享—国外ui设计优秀案例
国外企业更注重用户体验设计,倾向于简洁清晰的设计风格,以提高用户的使用体验和操作效率。他们注重“简约至上”的设计理念,认为简洁的设计可以减少用户的认知负担,提高用户的工作效率。 设计师在界面设计中往往更加注重创意性和个…...
在JavaScript中,改变this指向的call,apply,bind有什么区别,原理分别是什么?
在JavaScript中,call、apply和bind方法都是用来改变函数执行时this指向的。 以下通过一个Demo帮助理解,代码如下: var obj {name: lisi,sayHello: function() {console.log(this.name)} } obj.sayHello()// lisifunction sayHello() {conso…...
Redis 缓存策略详解:提升性能的四种常见模式
在现代分布式系统中,缓存是提升性能和减轻数据库负载的关键组件。Redis 作为一种高性能的内存数据库,被广泛应用于缓存层。本文将深入探讨几种常用的 Redis 缓存策略,包括旁路缓存模式(Cache-Aside Pattern)、读穿透模…...
怎么建设网站吸引并留住客户
如何建设网站吸引并留住客户 在当今数字化时代,网站是企业与客户沟通的重要桥梁。一个设计精良、功能完备的网站不仅能吸引客户的注意,还能有效留住他们。以下是一些建设网站的关键策略。 **1. 用户体验优先** 网站的整体用户体验(UX&#x…...
培训行业为什么要搭建自己的知识付费小程序平台?集师知识付费系统 集师知识付费小程序 集师知识服务系统 集师线上培训系统 集师线上卖课小程序
在当今这个信息爆炸的时代,培训行业正面临前所未有的变革与挑战。传统的线下授课模式虽然经典,但在互联网技术的冲击下,其局限性日益凸显。为了更好地适应市场需求,提升服务效率与用户体验,培训行业亟需搭建自己的知识…...
Linux:Linux进程概念
✨✨✨学习的道路很枯燥,希望我们能并肩走下来! 文章目录 目录 文章目录 前言 一 冯诺依曼体系结构 二 操作系统(Operator System) 2.1 概念 2.2 设计OS的目的 编辑 2.3 OS如何进行管理 编辑2.4 总结 三 进程的标示符 3.1 基本概念…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Linux中《基础IO》详细介绍
目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改,实现简单cat命令 输出信息到显示器,你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...
