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

代码随想录第三十八天(完全背包问题)|爬楼梯(第八期模拟笔试)|零钱兑换|完全平方数

爬楼梯(第八期模拟笔试)

该题也是昨天的完全背包排列问题,解法相同,将遍历顺序进行调换

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的最大值,才能保证在递推公式计算中被覆盖。

  1. dp[j]代表的是装满容量为j的背包所需的最少硬币数dp[j]
  2. 递推公式:dp[j]=min(dp[j],dp[j-coins[i]]+1);在这里需要先进行判断,因为dp[j]可能没有被重新计算覆盖,会为最大值,加1会循环到int的最小值加一。若是所有的dp[j]一定能由之前的状态推出的话,就不需要这个判断。
  3. 初始化:dp[0]=1,其他的都为Integer_MAX_VALUE
  4. 遍历顺序:这里是求的物品数,先遍历背包和先遍历物品都是一样的,只有求组合数的时候才有区别
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];}
}

相关文章:

代码随想录第三十八天(完全背包问题)|爬楼梯(第八期模拟笔试)|零钱兑换|完全平方数

爬楼梯&#xff08;第八期模拟笔试&#xff09; 该题也是昨天的完全背包排列问题&#xff0c;解法相同&#xff0c;将遍历顺序进行调换 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提示代码报错&#xff0c;项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…...

(双指针) 有效三角形的个数 和为s的两个数字 三数之和 四数之和

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 目录 文章目录 前言 一、有效三角形的个数&#xff08;medium&#xff09; 1.1、题目 1.2、讲解算法原理 1.3、编写代码 二、和为s的两个数字 2.1、题目 2.2、讲解算…...

力扣每日一题114:二叉树展开为链表

题目 中等 提示 给你二叉树的根结点 root &#xff0c;请你将它展开为一个单链表&#xff1a; 展开后的单链表应该同样使用 TreeNode &#xff0c;其中 right 子指针指向链表中下一个结点&#xff0c;而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同…...

Linux系统下使用LVM扩展逻辑卷的步骤指南

Linux系统下使用LVM扩展逻辑卷的步骤指南 文章目录 Linux系统下使用LVM扩展逻辑卷的步骤指南前言一、逻辑卷管理&#xff08;LVM&#xff09;简介二、扩展逻辑卷步骤1. 检查当前的磁盘布局2. 创建新的分区3. 更新内核的分区表4. 初始化新的物理卷5. 将物理卷添加到卷组6. 调整逻…...

探索AI编程新纪元:从零开始的智能编程之旅

提示&#xff1a;Baidu Comate 智能编码助手是基于文心大模型&#xff0c;打造的新一代编码辅助工具 文章目录 前言AI编程概述&#xff1a;未来已来场景需求&#xff1a;从简单到复杂&#xff0c;无所不包体验步骤&#xff1a;我的AI编程初探试用感受&#xff1a;双刃剑下的深思…...

RustGUI学习(iced)之小部件(三):如何使用下拉列表pick_list?

前言 本专栏是学习Rust的GUI库iced的合集,将介绍iced涉及的各个小部件分别介绍,最后会汇总为一个总的程序。 iced是RustGUI中比较强大的一个,目前处于发展中(即版本可能会改变),本专栏基于版本0.12.1. 概述 这是本专栏的第三篇,主要讲述下拉列表pick_list部件的使用,会…...

【OceanBase诊断调优】—— Unit 迁移问题的排查方法

适用版本&#xff1a;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 迁移的调度&#xff0c;如果…...

[极客大挑战 2019]PHP

1.通过目录扫描找到它的备份文件&#xff0c;这里的备份文件是它的源码。 2.源码当中涉及到的关键点就是魔术函数以及序列化与反序列化。 我们提交的select参数会被进行反序列化&#xff0c;我们要构造符合输出flag条件的序列化数据。 但是&#xff0c;这里要注意的就是我们提…...

数据结构之跳跃表

跳跃表 跳跃表&#xff08;skiplist&#xff09;是一种随机化的数据&#xff0c; 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出&#xff0c; 跳跃表以有序的方式在层次化的链表中保存元素&#xff0c; 效率和平衡树媲美 —— …...

搜维尔科技:动作捕捉解决方案:销售、服务、培训和支持

动作捕捉解决方案&#xff1a;销售、服务、培训和支持 搜维尔科技&#xff1a;动作捕捉解决方案&#xff1a;销售、服务、培训和支持l...

数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库(20240507)

数据库管理184期 2024-05-07 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库&#xff08;20240507&#xff09;1 JSON需求2 关系型表设计3 JSON关系型二元性视图3 查询视图总结 数据库管理-第184期 23ai:干掉MongoDB的不一定是另一个JSON数据库&#xff08;20…...

刷代码随想录有感(58):二叉树的最近公共祖先

题干&#xff1a; 代码&#xff1a; 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 浏览器插件入门

目录 前言 一&#xff0c;创建插件 1.创建一个新的目录 2.编写清单文件 二&#xff0c;高级清单文件 1.编写放置右窗口 2.常驻的后台JS或后台页面 3.event-pages 短周期使用 三&#xff0c;Chrome 扩展 API 函数 1.浏览器操作函数 2.内容脚本函数 3.后台脚本函数 4…...

在数字化转型的浪潮中,CBDB百数服务商如何破浪前行?

在信息化时代&#xff0c;传统咨询企业面临着数字化转型的挑战与机遇。如何利用数字化技术提升业务效率、增强客户黏性&#xff0c;成为了行业关注的焦点。云南析比迪彼企业管理有限公司&#xff08;CBDB&#xff09;作为云南地区的企业咨询服务提供商&#xff0c;率先与百数展…...

程序员的实用神器

在软件开发的海洋中&#xff0c;程序员的实用神器如同航海中的指南针&#xff0c;帮助他们导航、加速开发、优化代码质量&#xff0c;并最终抵达成功的彼岸。这些工具覆盖了从代码编写、版本控制到测试和部署的各个环节。然而&#xff0c;程序员们通常会有一套自己喜欢的工具集…...

spss 导入数据的时候 用于确定数据类型的值所在的百分比95%是什么意思,数据分析,医学数据分析

在SPSS中&#xff0c;当提及“数据类型的值所在的百分比95%”时&#xff0c;这通常与数据的统计分布或置信区间有关&#xff0c;而不是直接关于数据类型的定义。 导入数据的时候需要定义数据类型&#xff0c;那么根据提供的数据&#xff0c;来定义&#xff0c;有时候&#xff…...

Python进阶之-上下文管理器

✨前言&#xff1a; &#x1f31f;什么是上下文管理器&#xff1f; 在Python中&#xff0c;上下文管理器是支持with语句的对象&#xff0c;用于为代码块提供设置及清理代码。上下文管理器广泛应用于资源管理场景&#xff0c;例如文件操作、网络连接、数据库会话等&#xff0c…...

什么年代了,还在拿考勤说事

最近&#xff0c;看到了某公司的一项考勤规定&#xff1a;自然月内&#xff0c;事假累计超过3次或者累计请假时间超过8小时的&#xff0c;不予审批&#xff0c;强制休假的按旷工处理。 真的想吐槽&#xff0c;什么年代了&#xff0c;还在拿考勤说事&#xff0c;这是什么公司、什…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...