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

【代码训练营】day44 | 完全背包理论 518. 零钱兑换 II 377. 组合总和 Ⅳ

所用代码 java

完全背包

01背包物品只能使用一次 – 倒序遍历

for(i = 0; i < weight.length; i++){ 物品for (j = bagWeight; j >= weight[i]; j--){ 背包dp[j] = max(dp[j], dp[j-weight[i]] + value[i])}
}

完全背包物品可以使用无限次 – 正序遍历

for(i = 0; i < weight.length; i++){ 物品for (j = weight[i]; j <= bagWeight; j++){ 背包dp[j] = max(dp[j], dp[j-weight[i]] + value[i])}
}

完全背包for循环中可以颠倒,先遍历谁都可以

零钱兑换 II LeetCode 518

题目链接:零钱兑换 II LeetCode 518 - 中等

思路

  • dp[j]:装满背包j的情况有dp[j]种

  • 递推公式:dp[j] += dp[j-coins[i]]

  • 初始化:dp[0] = 1 如果等于0,后面累加就会一直是0, 空集也是一种方法

    • dp[1] += dp[0],1要从0得到结果然后继续累加
  • 遍历方向:coins[i] <= j <= amount

  • 打印dp

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]];
//                System.out.print("\tdp[j] = " + dp[j]);}
//            System.out.println();}return dp[amount];}
}

总结

先遍历物品,后遍历背包,保证了物品是从1、2、3开始的,不会有重复,也就是说这是一个组合数

若先遍历背包,再遍历物品,每次物品都是从1开始,就会有重复数,如1,2 2,1 但是这可以代表排列数

组合总和 Ⅳ leetCode 377

题目链接:组合总和 Ⅳ leetCode 377 - 中等

思路

  • dp[j] :和为j的情况有dp[j]种
  • 递推:dp[j] += dp[j-nums[i]]
  • 初始化:dp[0] = 1
  • 遍历顺序:先背包,后物品
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]];System.out.print("\tdp[j] = " +dp[j]);}System.out.println();}return dp[target];}
}

总结

背包为0可以装下物品 1 2 3 这其实是一个悖论,也可以认为是背包为0的可以装下无限大的东西。但是我认为把这个看成一个初始化无意义的值就行了,以防止出现后序累加的值一直为0。

dp数组的打印值

        dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 2   dp[j] = 2dp[j] = 2   dp[j] = 3   dp[j] = 4dp[j] = 4   dp[j] = 6   dp[j] = 7

若是觉得这值确实没必要,我们其实可以从j=1开始遍历,所打印的值就有助于对于dp数组的理解。

        dp[j] = 1   dp[j] = 1   dp[j] = 1dp[j] = 1   dp[j] = 2   dp[j] = 2dp[j] = 2   dp[j] = 3   dp[j] = 4dp[j] = 4   dp[j] = 6   dp[j] = 7

所以,通过这两个题,我们可以明白:

  • 先遍历物品,再遍历背包:组合问题 - 无重复
  • 先遍历背包,再遍历物品:排列数 - 有重复(可排序)

相关文章:

【代码训练营】day44 | 完全背包理论 518. 零钱兑换 II 377. 组合总和 Ⅳ

所用代码 java 完全背包 01背包物品只能使用一次 – 倒序遍历 for(i 0; i < weight.length; i){ 物品for (j bagWeight; j > weight[i]; j--){ 背包dp[j] max(dp[j], dp[j-weight[i]] value[i])} }完全背包物品可以使用无限次 – 正序遍历 for(i 0; i < weigh…...

ICA简介:独立成分分析

1. 简介 您是否曾经遇到过这样一种情况&#xff1a;您试图分析一个复杂且高度相关的数据集&#xff0c;却对信息量感到不知所措&#xff1f;这就是独立成分分析 (ICA) 的用武之地。ICA 是数据分析领域的一项强大技术&#xff0c;可让您分离和识别多元数据集中的底层独立来源。 …...

②【Java 组】蓝桥杯省赛真题解析 [振兴中华] [三部排序] 持续更新中...

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ 蓝桥杯真题--持续更新中...一、振兴中华二、三…...

PostgreSql 视图

一、概述 视图&#xff08;View&#xff09;本质上是一个存储在数据库中的查询语句。视图本身不包含数据&#xff0c;也被称为虚拟表。 我们在创建视图时给它指定了一个名称&#xff0c;然后可以像表一样对其进行查询。 优势&#xff1a; 不保存数据&#xff0c;节省空间。减少…...

【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分)

【PAT甲级题解记录】1150 Travelling Salesman Problem (25 分) 前言 Problem&#xff1a;1150 Travelling Salesman Problem (25 分) Tags&#xff1a;模拟 图的遍历 旅行商问题 Difficulty&#xff1a;剧情模式 想流点汗 想流点血 死而无憾 Address&#xff1a;1150 Travell…...

vue生命周期

vue生命周期是什么&#xff1f;Vue生命周期是指vue实例对象从创建之初到销毁的过程&#xff0c;vue所有功能的实现都是围绕其生命周期进行的&#xff0c;在生命周期的不同阶段调用对应的钩子函数可以实现组件数据管理和DOM渲染两大重要功能。我们来看一下官网给的vue生命周期的…...

排查解决Java进程占用内存过高

排查解决Java进程占用内存过高1 在项目部署运行之前1 检查JVM参数设置2 检查代码逻辑3 使用内存分析工具4 检查线程5 调整应用程序的设计7 调整硬件资源2 在项目部署运行之后1 在项目部署运行之前 1 检查JVM参数设置 检查JVM的启动参数设置&#xff0c;包括-Xmx和-Xms参数&am…...

一个基于 LKM 的 Linux 内核级 rootkit 的实现

博客已迁移至&#xff1a;https://gls.show/ GitHub链接 演示Slides overview rootkit是一种恶意软件&#xff0c;攻击者可以在获得 root 或管理员权限后安装它&#xff0c;从而隐藏入侵并保持root权限访问。rootkit可以是用户级的&#xff0c;也可以是内核级的。关于rootk…...

CAN工具 - ValueCAN - 基础介绍(续)

VSpy3&#xff08;Vehicle Spy 3的简写&#xff09;&#xff0c;作为一个常用的车载总线仿真工具&#xff0c;在车载网络领域也是有非常大的市场&#xff0c;前面也简单介绍过一些简单的功能&#xff0c;今天就再次介绍一些。什么是VSpy3&#xff1f;VSpy3是美国英特佩斯公司下…...

一个Laravel+vue免费开源的基于RABC控制的博客系统

项目介绍 CCENOTE 是一个使用 Vue3 Laravel8 开发的前后端分离的基于RABC权限控制管理的内容管理系统&#xff0c;由于作者本人比较喜欢写作的原因&#xff0c;因此开发了这个项目&#xff0c;后端使用的PHP的Laravel框架&#xff0c;并且整理了数据层与业务层&#xff0c;相…...

从 B 站出发,用 Chrome devTools performance 分析页面如何渲染

页面是如何渲染的&#xff1f;通常会得到“解析 HTML、css 合成 Render Tree&#xff0c;就可以渲染了”的回答。但是具体都做了些什么&#xff0c;却很少有人细说&#xff0c;我们今天就从 Chrome 的性能工具开始&#xff0c;具体看看一个页面是如何进行渲染的&#xff0c;以及…...

Java异常Throwable的分类

1. Exception&#xff1a;程序本身可以捕获并且可以处理的异常 编译时异常&#xff1a;编译期就会检查的异常&#xff0c;若调用的方法中throw了此类异常&#xff0c;则必须进行显式处理处理&#xff08;用try…catch捕获或者throws向上抛出&#xff09;&#xff0c;否则无法通…...

【mybatis的#和$使用和区别】

MyBatis是一种基于Java的持久层框架&#xff0c;用于将数据库操作和Java对象之间的映射进行处理。在MyBatis中&#xff0c;#和 $ 符号是用于SQL语句中的占位符。 在SQL语句中&#xff0c;#和 $ 符号都表示占位符&#xff0c;但它们的使用方式略有不同&#xff1a; # 符号 #符…...

感知趋势,洞察发展:2023(第十届)趋势与预测大会成功举办

2023年2月23日&#xff0c;运联年会&#xff1a;2023&#xff08;第十届&#xff09;趋势与预测大会在深圳机场凯悦酒店成功闭幕。自2014年开始&#xff0c;“运联年会&#xff1a;趋势与预测”已经连续举办九届。这场大会&#xff0c;既是一次行业性的“年终总结”&#xff0c…...

Spring-Aop核心技术

前言spring一直以来都是我们Java开发中最核心的一个技术&#xff0c;其中又以ioc和aop为主要技术&#xff0c;本篇文章主要讲一下aop的核心技术&#xff0c;也就是ProxyFactory技术的使用&#xff0c;而基本的jdk动态代理和cglib代理技术并不涉及&#xff0c;如有需要&#xff…...

webpack常用优化原理剖析

webpack常用优化原理剖析 按需加载代码配置原理CDN加速-externals代码配置GZIP压缩代码配置原理Tree Shaking代码配置原理按需加载 把不同路由对应的组件分割成不同的代码块,然后当路由被访问的时候才加载对应组件. 代码配置 //定义了一个异步函数,由于函数不调用不执行,所…...

【现在努力还不晚】--MySQL数据库的数据模型

目录 1、关系型数据库&#xff08;RDBMS&#xff09; 特点 2、数据模型 在学习MySQL之前要了解一下数据库的数据模型&#xff0c;我们就知道在MySQL当中&#xff0c;数据是如何存储的&#xff0c;我们了解一下概念&#xff01; 1、关系型数据库&#xff08;RDBMS&#xff0…...

二手商品交易网站

技术&#xff1a;Java、JSP等摘要&#xff1a;随着科学技术和信息通讯的飞速发展&#xff0c;Internet极大地丰富和改变着我们生活的各个行业。随着Internet的普及应用&#xff0c;人们可以跨越时间和空间的限制&#xff0c;足不出户便能通过网络完成信息交流&#xff0c;而完成…...

第三阶段04-同步请求和异步请求,get/post,Josn,pojo,Session/Cookie,过滤器Filter

文章目录同步请求和异步请求客户端如何发出异步请求自定义模板代码Get和Post请求异步版本的注册和登录商品管理系统(异步版本)商品列表步骤:前后端分离为什么需要前后端分离?为什么以后不再使用同步请求?JSONPOJO会话对象Session如何记住登录状态后端的MVC会话管理Cookie通过…...

Spark学习:spark相似算子解析

spark算子 一、Map、Flatmap和MapPartition二、repartition和coalesce三、reduceByKey和groupByKey四、collect、take和first一、Map、Flatmap和MapPartition 算子作用map接收一个高阶函数f,对每个算子进行f操作flatmap接收一个高阶函数f,对每个元素进行f操作,形成一个大的集合…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...