代码随想录第三十八天(完全背包问题)|爬楼梯(第八期模拟笔试)|零钱兑换|完全平方数
爬楼梯(第八期模拟笔试)
该题也是昨天的完全背包排列问题,解法相同,将遍历顺序进行调换
import java.util.*;
public class Main{public static void main (String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt();int m=sc.nextInt();int[] step=new int[m+1];for(int i=0;i<m+1;i++){step[i]=i;}maxMethod(n,step);}public static void maxMethod(int target,int[] step){int[] dp=new int[target+1];dp[0]=1;for(int j=1;j<target+1;j++){for(int i=0;i<step.length;i++){if(j>=step[i]){dp[j]+=dp[j-step[i]];}}}System.out.println(dp[target]);}
}
零钱兑换
这一题也是求放入背包中的物品数,但是不是就放满指定容量背包的最大物品数,而是最小物品数。求最少物品数和最大物品数的区别在于两个地方,一个是递推公式,还有就是初始化,因为要求最小物品数,所以除了dp[0]以外,所有的元素都需要初始化成int的最大值,才能保证在递推公式计算中被覆盖。
- dp[j]代表的是装满容量为j的背包所需的最少硬币数dp[j]
- 递推公式:dp[j]=min(dp[j],dp[j-coins[i]]+1);在这里需要先进行判断,因为dp[j]可能没有被重新计算覆盖,会为最大值,加1会循环到int的最小值加一。若是所有的dp[j]一定能由之前的状态推出的话,就不需要这个判断。
- 初始化:dp[0]=1,其他的都为Integer_MAX_VALUE
- 遍历顺序:这里是求的物品数,先遍历背包和先遍历物品都是一样的,只有求组合数的时候才有区别
import java.util.*;
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;}for(int i=0;i<coins.length;i++){for(int j=coins[i];j<amount+1;j++){//因为此时初始值都为int的最大值,再加一的话会变成int的最小值+1;所以要判断if(dp[j-coins[i]]!=Integer.MAX_VALUE){dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount]==Integer.MAX_VALUE){return -1;}else{return dp[amount];}}
}
完全平方数
这一题和上面一题解法一样,只是要先将完全平方数求出。再进行动规计算
class Solution {public int numSquares(int n) {List<Integer> arr=new ArrayList();for(int i=0;i<=n;i++){double j=Math.sqrt(i);if(j%1==0){arr.add(i);}}int[] nums=new int[arr.size()];for(int i=0;i<nums.length;i++){nums[i]=arr.get(i);}int[] dp=new int[n+1];for(int i=1;i<n+1;i++){dp[i]=Integer.MAX_VALUE;}for(int i=0;i<nums.length;i++){for(int j=nums[i];j<n+1;j++){if(dp[j-nums[i]]!=Integer.MAX_VALUE){dp[j]=Math.min(dp[j],dp[j-nums[i]]+1);}}}return dp[n];}
}
相关文章:
代码随想录第三十八天(完全背包问题)|爬楼梯(第八期模拟笔试)|零钱兑换|完全平方数
爬楼梯(第八期模拟笔试) 该题也是昨天的完全背包排列问题,解法相同,将遍历顺序进行调换 import java.util.*; public class Main{public static void main (String[] args) {Scanner scnew Scanner(System.in);int nsc.nextInt(…...
idea常用知识点随记
idea常用知识点随记 1. 打开idea隐藏的commit窗口2. idea中拉取Git分支代码3. idea提示代码报错,项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…...
(双指针) 有效三角形的个数 和为s的两个数字 三数之和 四数之和
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 文章目录 前言 一、有效三角形的个数(medium) 1.1、题目 1.2、讲解算法原理 1.3、编写代码 二、和为s的两个数字 2.1、题目 2.2、讲解算…...
力扣每日一题114:二叉树展开为链表
题目 中等 提示 给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同…...
Linux系统下使用LVM扩展逻辑卷的步骤指南
Linux系统下使用LVM扩展逻辑卷的步骤指南 文章目录 Linux系统下使用LVM扩展逻辑卷的步骤指南前言一、逻辑卷管理(LVM)简介二、扩展逻辑卷步骤1. 检查当前的磁盘布局2. 创建新的分区3. 更新内核的分区表4. 初始化新的物理卷5. 将物理卷添加到卷组6. 调整逻…...
探索AI编程新纪元:从零开始的智能编程之旅
提示:Baidu Comate 智能编码助手是基于文心大模型,打造的新一代编码辅助工具 文章目录 前言AI编程概述:未来已来场景需求:从简单到复杂,无所不包体验步骤:我的AI编程初探试用感受:双刃剑下的深思…...
RustGUI学习(iced)之小部件(三):如何使用下拉列表pick_list?
前言 本专栏是学习Rust的GUI库iced的合集,将介绍iced涉及的各个小部件分别介绍,最后会汇总为一个总的程序。 iced是RustGUI中比较强大的一个,目前处于发展中(即版本可能会改变),本专栏基于版本0.12.1. 概述 这是本专栏的第三篇,主要讲述下拉列表pick_list部件的使用,会…...
【OceanBase诊断调优】—— Unit 迁移问题的排查方法
适用版本:V2.1.x、V2.2.x、V3.1.x、V3.2.x 本文主要介绍 OceanBase 数据集在副本迁移过程中遇到的问题的排查方法。 适用版本 V2.1.x、V2.2.x、V3.1.x、V3.2.x 手动调度迁移问题的排查 OceanBase 数据库的 RootService 模块负责 Unit 迁移的调度,如果…...
[极客大挑战 2019]PHP
1.通过目录扫描找到它的备份文件,这里的备份文件是它的源码。 2.源码当中涉及到的关键点就是魔术函数以及序列化与反序列化。 我们提交的select参数会被进行反序列化,我们要构造符合输出flag条件的序列化数据。 但是,这里要注意的就是我们提…...
数据结构之跳跃表
跳跃表 跳跃表(skiplist)是一种随机化的数据, 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳跃表以有序的方式在层次化的链表中保存元素, 效率和平衡树媲美 —— …...
搜维尔科技:动作捕捉解决方案:销售、服务、培训和支持
动作捕捉解决方案:销售、服务、培训和支持 搜维尔科技:动作捕捉解决方案:销售、服务、培训和支持l...
数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20240507)
数据库管理184期 2024-05-07 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20240507)1 JSON需求2 关系型表设计3 JSON关系型二元性视图3 查询视图总结 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20…...
刷代码随想录有感(58):二叉树的最近公共祖先
题干: 代码: class Solution { public:TreeNode* traversal(TreeNode* root, TreeNode* p, TreeNode* q){if(root NULL)return NULL;if(root p || root q)return root;TreeNode* left traversal(root->left, p, q);TreeNode* right traversal(r…...
[开发|安卓] Android Studio 开发环境配置
Android Studio下载 Android Studio下载地址 下载SDK依赖 1.点击左上角菜单 2.选择工具 3.打开SDK管理中心 4.下载项目目标Android版本的SDK 配置安卓虚拟机 1.打开右上角的设备管理 2.选择合适的手机规格 3.下载并选择项目目标Android系统 4.点击完成配置 …...
开发 Chrome 浏览器插件入门
目录 前言 一,创建插件 1.创建一个新的目录 2.编写清单文件 二,高级清单文件 1.编写放置右窗口 2.常驻的后台JS或后台页面 3.event-pages 短周期使用 三,Chrome 扩展 API 函数 1.浏览器操作函数 2.内容脚本函数 3.后台脚本函数 4…...
在数字化转型的浪潮中,CBDB百数服务商如何破浪前行?
在信息化时代,传统咨询企业面临着数字化转型的挑战与机遇。如何利用数字化技术提升业务效率、增强客户黏性,成为了行业关注的焦点。云南析比迪彼企业管理有限公司(CBDB)作为云南地区的企业咨询服务提供商,率先与百数展…...
程序员的实用神器
在软件开发的海洋中,程序员的实用神器如同航海中的指南针,帮助他们导航、加速开发、优化代码质量,并最终抵达成功的彼岸。这些工具覆盖了从代码编写、版本控制到测试和部署的各个环节。然而,程序员们通常会有一套自己喜欢的工具集…...
spss 导入数据的时候 用于确定数据类型的值所在的百分比95%是什么意思,数据分析,医学数据分析
在SPSS中,当提及“数据类型的值所在的百分比95%”时,这通常与数据的统计分布或置信区间有关,而不是直接关于数据类型的定义。 导入数据的时候需要定义数据类型,那么根据提供的数据,来定义,有时候ÿ…...
Python进阶之-上下文管理器
✨前言: 🌟什么是上下文管理器? 在Python中,上下文管理器是支持with语句的对象,用于为代码块提供设置及清理代码。上下文管理器广泛应用于资源管理场景,例如文件操作、网络连接、数据库会话等,…...
什么年代了,还在拿考勤说事
最近,看到了某公司的一项考勤规定:自然月内,事假累计超过3次或者累计请假时间超过8小时的,不予审批,强制休假的按旷工处理。 真的想吐槽,什么年代了,还在拿考勤说事,这是什么公司、什…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
HTTPS证书一年多少钱?
HTTPS证书作为保障网站数据传输安全的重要工具,成为众多网站运营者的必备选择。然而,面对市场上种类繁多的HTTPS证书,其一年费用究竟是多少,又受哪些因素影响呢? 首先,HTTPS证书通常在PinTrust这样的专业平…...
