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

算法通关村-----动态规划高频问题

最少硬币数问题

问题描述

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。你可以认为每种硬币的数量是无限的。详见leetcode322

问题分析

设f(n)为amount=n时使用的最少金币数。遍历coins数组,选择f(n-coins[i])(i=0,1,coins.length-1)的最小值,即为需要的最少硬币数,递归继续寻找f(n-coins[i])的最小值,初始时f(0)=0,如果一些总金额无法凑成时,可以使用amount+1填充数组。

代码实现

public int coinChange(int[] coins, int amount) {int[] res = new int[amount+1];int max = amount+1;Arrays.fill(res,max);res[0] = 0;int[] temp = new int[coins.length];for(int i=1;i<amount+1;i++){for(int j=0;j<coins.length;j++){int leftAmount = i - coins[j];temp[j] = leftAmount>=0?res[leftAmount]+1:max;}int min = max;for(int j=0;j<coins.length;j++){min = Math.min(temp[j],min);}res[i]= min;}if(res[amount]==max){return -1;}return res[amount];
}

最长连续递增子序列

问题描述

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。详见leetcode674

问题分析

这道题,我们之前使用滑动窗口的方式也可以解决,使用动态规划解题时,对于连续递增子序列的最后一个元素nums[k],存在两种情况,第一种是最长连续递增子序列长度为1,连续递增子序列只包含一个元素nums[k],第二种是存在k-1,使得nums[k-1]<num[k],设f[k]为到下标k处的连续递增子序列长度,则,如果nums[k-1]>=nums[k],f[k]=1,否则f[k]=f[k-1]+1,初始值f[0]=1,

代码实现

滑动窗口实现

public int findLengthOfLCIS(int[] nums) {     if(nums.length==0||nums.length==1){return nums.length;}int res = 1;int count =1;for(int i=1;i<nums.length;i++){if(nums[i-1]>=nums[i]){count =1;}else{count++;}if(count>res){res = count;}}return res;   
}

动态规划实现

public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);int max = 1;for(int i=1;i<nums.length;i++){if(nums[i]>nums[i-1]){dp[i] = dp[i-1]+1;max = Math.max(dp[i],max);}}return max;
}

最长递增子序列

问题描述

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。详见leetcode300

问题分析

这道题与上一题相似,只是不需要连续递增。对于最长递增子序列的最后一个元素nums[k],存在两种情况,第一种是最长连续递增子序列长度为1,连续递增子序列只包含一个元素nums[k],第二种是存在i,使得i<k,nums[i]<num[k],设f[k]为到下标k处的连续递增子序列长度,则f[k] = max{f[i]+1}(i是所有nums[i]<nums[k]的集合)

代码实现

public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp,1);for(int i=1;i<nums.length;i++){for(int j=i-1;j>=0;j--){if(nums[j]<nums[i]&&dp[j]+1>dp[i]){dp[i] = dp[j]+1;}}}int max = 1;for(int i=0;i<nums.length;i++){max = Math.max(max,dp[i]);}return max;
}

最少完全平方数

问题描述

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。详见leetcode279

问题分析

设f(n)表示和为 n 的完全平方数的最少数量 。则f(n)=min{f(n-jj)+1}(j是满足所有jj<=n的j的集合).初始时f(0) = 0.

代码实现

public int numSquares(int n) {int[] f = new int[n+1];Arrays.fill(f,Integer.MAX_VALUE);f[0] = 0;for(int i=1;i<n+1;i++){for(int j=1;j*j<=i;j++){if(f[i-j*j]+1<f[i]){f[i] = f[i-j*j]+1;}}}return f[n];
}

跳跃游戏

问题描述

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。详见leetcode55

问题分析

设f(n)是一个boolean数组,为true表示可以跳到数组下标n处,为false表示无法跳到数组下标n处。f(n)为true的条件是f(i)为true,n-1-i<nums[i],初始时f(0)=true

public boolean canJump(int[] nums) {boolean[] f = new boolean[nums.length];Arrays.fill(f,false);f[0] = true;for(int i=1;i<nums.length;i++){for(int j=0;j<i;j++){if(f[j]&&j+nums[j]>=i){f[i] = true;break;}}} return f[nums.length-1];
}

总结

这部分动态规划问题需要我们你想推导,即如何由我们想要结果的前一个状态得到我们想要的结果(往往是最值,所以涉及从前面多个状态到当前状态的选择)。逆向推导得到状态转移方程f,确定初始条件,一步步填充dp数组,最终得到我们想要的结果并返回。

相关文章:

算法通关村-----动态规划高频问题

最少硬币数问题 问题描述 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -1 。你可以认为每种硬…...

记一起小意外事件引起的批量重命名文件名

一、事件描述 某次,因某业务系统迁移,一线人员对业务目录误操作,执行打包命令过程中导致Tomcat下的web应用程序无法使用,检查后发现项目下所有文件名都加了gz格式;询问一线,发现是对项目目录执行了:gzip -r ./tomcat导致程序文件找不到;报错如下: 二、事件处理 1、查看…...

【Excel函数】Excel的Len函数求对象的字符数

在Excel中&#xff0c;LEN函数用于计算文本字符串中的字符数。它的语法如下。 LEN(text) 其中&#xff0c;text是要计算字符数的文本字符串。 例如&#xff0c;如果你想计算单元格A1中文本的字符数&#xff0c;可以使用以下公式&#xff1a; A2len(a1) 结果将返回单元格A1中文…...

小白备战大厂算法笔试(八)——搜索

搜索 二分查找 二分查找是一种基于分治策略的高效搜索算法。它利用数据的有序性&#xff0c;每轮减少一半搜索范围&#xff0c;直至找到目标元素或搜索区间为空为止。 Question&#xff1a; 给定一个长度为n的数组 nums &#xff0c;元素按从小到大的顺序排列&#xff0c;数组…...

〔022〕Stable Diffusion 之 生成视频 篇

✨ 目录 &#x1f388; 视频转换 / mov2mov&#x1f388; 视频转换前奏准备&#x1f388; 视频转换 mov2mov 使用&#x1f388; 视频转换 mov2mov 效果预览&#x1f388; 视频无限缩放 / Infinite Zoom&#x1f388; 视频无限缩放 Infinite Zoom 使用 &#x1f388; 视频转换 /…...

网络安全深入学习第三课——热门框架漏洞(RCE—Struts2远程代码执行)

文章目录 一、Struts2框架介绍二、Struts2远程代码执行漏洞三、Struts2执行代码的原理四、Struts2框架特征五、漏洞手工POC六、漏洞工具复现 一、Struts2框架介绍 ------ Struts2是apache项目下的一个web 框架&#xff0c;普遍应用于阿里巴巴、京东等互联网、政府、企业门户网…...

【uni-app】

准备工作&#xff08;Hbuilder&#xff09; 1.下载hbuilder&#xff0c;插件使用Vue3的uni-app项目 2.需要安装编译器 3.下载微信开发者工具 4.点击运行->微信开发者工具 5.打开微信开发者工具的服务端口 效果图 准备工作&#xff08;VScode&#xff09; 插件 uni-cr…...

Pytorch 多卡并行(3)—— 使用 DDP 加速 minGPT 训练

前文 并行原理简介和 DDP 并行实践 和 使用 torchrun 进行容错处理 在简单的随机数据上演示了使用 DDP 并行加速训练的方法&#xff0c;本文考虑一个更加复杂的 GPT 类模型&#xff0c;说明如何进行 DDP 并行实战MinGPT 是 GPT 模型的一个流行的开源 PyTorch 复现项目&#xff…...

IAM、EIAM、CIAM、RAM、IDaaS 都是什么?

后端程序员在做 ToB 产品或者后台系统时&#xff0c;都不可避免的会遇到账号系统、登录系统、权限系统、日志系统等这些核心功能。这些功能一般都是以 SSO 系统、RBAC 权限管理系统等方式命名&#xff0c;但这些系统合起来有一个专有名词&#xff1a;IAM。 IAM IAM 是 Identi…...

STM32 Cubemx 通用定时器 General-Purpose Timers同步

文章目录 前言简介cubemx配置 前言 持续学习stm32中… 简介 通用定时器是一个16位的计数器&#xff0c;支持向上up、向下down与中心对称up-down三种模式。可以用于测量信号脉宽&#xff08;输入捕捉&#xff09;&#xff0c;输出一定的波形&#xff08;比较输出与PWM输出&am…...

Ubuntu 20.04降级clang-format

1. 卸载clang-format sudo apt purge clang-format 2. 安装clang-format-6.0 sudo apt install clang-format-6.0 3. 软链接clang-format sudo ln -s /usr/bin/clang-format-6.0 /usr/bin/clang-format...

激活函数总结(三十四):激活函数补充(FReLU、CReLU)

激活函数总结&#xff08;三十四&#xff09;&#xff1a;激活函数补充 1 引言2 激活函数2.1 FReLU激活函数2.2 CReLU激活函数 3. 总结 1 引言 在前面的文章中已经介绍了介绍了一系列激活函数 (Sigmoid、Tanh、ReLU、Leaky ReLU、PReLU、Swish、ELU、SELU、GELU、Softmax、Sof…...

【LeetCode-简单题KMP】459. 重复的子字符串

文章目录 题目方法一&#xff1a;移动匹配方法二&#xff1a;KMP算法 题目 方法一&#xff1a;移动匹配 class Solution {//移动匹配public boolean repeatedSubstringPattern(String s) {StringBuffer str new StringBuffer(s);//ababstr.append(s);//拼接一份自己 abababab…...

Lua脚本

基本语法 注释 print(“script lua win”) – 单行注释 – [[ 多行注释 ]] – 标识符 类似于&#xff1a;java当中 变量、属性名、方法名。 以字母&#xff08;a-z,A-Z&#xff09;、下划线 开头&#xff0c;后面加上0个或多个 字母、下划线、数字。 不要用下划线大写字母…...

vue 封装一个Dialog组件

基于element-plus封装一个Dialog组件 <template><section class"dialog-wrap"><el-dialog :title"title" v-model"visible" :close-on-click-modal"false"><section class"content-wrap"><Form…...

外包干了2个月,技术退步明显。。。。。

先说一下自己的情况&#xff0c;大专生&#xff0c;18年通过校招进入武汉某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...

python科研作图

1、气泡图 气泡图是一种在xy轴上显示三个维度的数据的有效方式。在气泡图中&#xff0c;基本上&#xff0c;每个气泡代表一个数据点。横坐标和纵坐标的位置代表两个维度&#xff0c;气泡的大小则代表第三个维度。 在这个例子中&#xff0c;我们用numpy库生成了一些随机数据&a…...

视锥体裁剪射线的算法

射线Ray(直线情况)需要满足的条件: 在视野中显示的粗细均匀,需要分段绘制,每段的粗细根据到视野的距离计算射线model的顶点尽量少以节省性能损耗要满足条件2的话需要对射线进行裁剪,只绘制射线在视锥体内的部分,因此需要计算射线被视锥体裁剪后新的起点和终点 1. 计算三角…...

程序员在线周刊(投稿篇)

嗨&#xff0c;大家好&#xff01;作为一名程序员&#xff0c;并且是一名互联网文章作者&#xff0c;我非常激动地向大家宣布&#xff0c;我们计划推出一份在线周刊&#xff0c;专门为程序员们提供有趣、实用的文章和资讯。而现在&#xff0c;我们正在征集投稿&#xff01; 是…...

uniapp——实现聊天室功能——技能提升

这里写目录标题 效果图聊天室功能代码——html部分代码——js部分代码——其他部分 首先声明一点&#xff1a;下面的内容是从一个uniapp的程序中摘录的&#xff0c;并非本人所写&#xff0c;先做记录&#xff0c;以免后续遇到相似需求抓耳挠腮。 效果图 聊天室功能 发送图片 …...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...