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

动态规划技巧点

动规五部曲(来自b站卡哥):1、确定DP数组中i、j…的含义。2、确定DP推导式。3、DP数组初始化。4、DP数组遍历顺序。5、DP数组打印校验。

  • 父问题、子问题有些许区别:LeetCode343.整数拆分
    今天在哔哩哔哩上刷到了一个非常有意思的leetcode整数拆分的题,博主利用动态规划。我暂时没有想到动态规划来求解,因此先尝试一下记忆性递归,没想到击败100%用户,暂时不清楚leetcode屏蔽逻辑。该题并不是很难,但有一个递归技巧点,因此进行记录。
class Solution {public int integerBreak(int n) {return integerBreakBy(n, new int[n], true);}public int integerBreakBy(int i, int[] data, boolean flag){if(i <= 1){return 1;}int max = -1;int a = flag ? i - 1 : i;for(int j = 1; j <= a; j++){int i_j = 0;if(data[i - j] == 0)data[i - j] = integerBreakBy(i - j, data, false);int cur_data = j * data[i - j];max = max < cur_data ? cur_data : max;  }return max;}
}

由于该题解要求拆出的数字个数要大于1,但是在子递归中,不用进行拆分就也是可以的,因此,引入了一个flag参数,当第一次进行拆分的时候,只要拆分出两个,子问题没有这条限制,所以引入了一个flag。

  • dp数组中记录的不一定是整体最优,可能是是包含当前值的最优值,全局最优就可以利用一个变量来记录各个局部最优 300.最长递增子序列
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];dp[0] = 1;int max_value = 0;for(int i = 0; i < nums.length; i++){dp[i] = 1;for(int j = 0; j < i; j++){if(nums[i] > nums[j]){dp[i] = Math.max(dp[i], dp[j] + 1);}// dp[i] = Math.max(dp[i], nums[i] > nums[j] ? dp[j] + 1 : 1);}if(dp[i] > max_value)max_value = dp[i];}return max_value;}
}

以上问题中,dp数组并非记录的是全局最优,而是必须包含当前数字的局部最优。全局最优利用max_value来进行记录。一维dp中,很多需要子遍历的(即第二层遍历j)。

相关文章:

动态规划技巧点

动规五部曲&#xff08;来自b站卡哥&#xff09;&#xff1a;1、确定DP数组中i、j…的含义。2、确定DP推导式。3、DP数组初始化。4、DP数组遍历顺序。5、DP数组打印校验。 父问题、子问题有些许区别&#xff1a;LeetCode343.整数拆分 今天在哔哩哔哩上刷到了一个非常有意思的l…...

深度学习之pytorch常见的学习率绘制

文章目录 0. Scope1. StepLR2. MultiStepLR3. ExponentialLR4. CosineAnnealingLR5. ReduceLROnPlateau6. CyclicLR7. OneCycleLR小结参考文献 https://blog.csdn.net/coldasice342/article/details/143435848 0. Scope 在深度学习中&#xff0c;学习率&#xff08;Learning R…...

Spring Boot集成SQL Server快速入门Demo

1.什么是SQL Server&#xff1f; SQL Server是由Microsoft开发和推广的以客户/服务器&#xff08;c/s&#xff09;模式访问、使用Transact-SQL语言的关系数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;它最初是由Microsoft、Sybase和Ashton-Tate三家公司共同开发的&…...

低代码牵手 AI 接口:开启智能化开发新征程

一、低代码与 AI 接口的结合趋势 低代码开发平台近年来在软件开发领域迅速崛起。随着企业数字化转型的需求不断增长&#xff0c;低代码开发平台以其快速构建应用程序的优势&#xff0c;满足了企业对高效开发的需求。例如&#xff0c;启效云低代码平台通过范式化和高颗粒度的可配…...

【已解决】git push一直提示输入用户名及密码、fatal: Could not read from remote repository的问题

问题描述&#xff1a; 在实操中&#xff0c;git push代码到github上一直提示输入用户名及密码&#xff0c;并且跳出的输入框输入用户名和密码后&#xff0c;报错找不到远程仓库 实际解决中&#xff0c;发现我环境有两个问题解决&#xff1a; git push一直提示输入用户名及密码…...

python语言基础-4 常用模块-4.13 其他模块

声明&#xff1a;本内容非盈利性质&#xff0c;也不支持任何组织或个人将其用作盈利用途。本内容来源于参考书或网站&#xff0c;会尽量附上原文链接&#xff0c;并鼓励大家看原文。侵删。 4.13 其他模块 除此之外python中还有大量的功能模块&#xff0c;如&#xff1a; pill…...

微信小程序=》基础=》常见问题=》性能总结

文章目录 微信小程序开发应用 实例小程序生命周期 以及 各生命周期应用实例小程序图片 展示方案 小程序打包应用方案技术细节&#xff08;分包应用实例&#xff09;技术细节&#xff08;压缩处理&#xff09;一、准备工作二、JavaScript 代码压缩三、WXML 文件优化&#xff08…...

JWT深度解析:Java Web中的安全传输与身份验证

标题&#xff1a;JWT深度解析&#xff1a;Java Web中的安全传输与身份验证 引言 JSON Web Token&#xff08;JWT&#xff09;是一种轻量级的身份验证和授权标准&#xff0c;它允许在各方之间安全地传输信息。在Java Web开发中&#xff0c;JWT因其无状态、可扩展性和跨域支持而…...

使用Java爬虫获取商品订单详情:从API到数据存储

在电子商务日益发展的今天&#xff0c;获取商品订单详情成为了许多开发者和数据分析师的需求。无论是为了分析用户行为&#xff0c;还是为了优化库存管理&#xff0c;订单数据的获取都是至关重要的。本文将详细介绍如何使用Java编写爬虫&#xff0c;通过API获取商品订单详情&am…...

Mybatis中批量插入foreach优化

数据库批量入库方常见方式&#xff1a;Java中foreach和xml中使用foreach 两者的区别&#xff1a; 通过Java的foreach循环批量插入&#xff1a; 当我们在Java通过foreach循环插入的时候&#xff0c;是一条一条sql执行然后将事物统一交给spring的事物来管理&#xff08;Transa…...

Word VBA如何间隔选中多个(非连续)段落

实例需求&#xff1a;Word文档中的有多个段落&#xff0c;段落总数量不确定&#xff0c;现在需要先选中所有基数段落&#xff0c;即&#xff1a;段落1&#xff0c;段落3 … &#xff0c;然后一次性设置粗体格式。 也许有的读者会认为这个无厘头的需求&#xff0c;循环遍历遍历文…...

Linux系统常用操作与命令指南

一、快捷分类 1、移动光标 h&#xff0c; j&#xff0c; k&#xff0c; l 左&#xff0c; 下&#xff0c; 上&#xff0c; 右 Ctrl-F:下翻一页 Ctrl-B:上翻一页 Ctrl-U:上翻半页 Ctrl-d:下翻半页 0:跳至行首&#xff0c;不管有无缩进&#xff0c;就是跳到第0个字…...

StructuredStreaming (一)

一、sparkStreaming的不足 1.基于微批,延迟高不能做到真正的实时 2.DStream基于RDD,不直接支持SQL 3.流批处理的API应用层不统一,(流用的DStream-底层是RDD,批用的DF/DS/RDD) 4.不支持EventTime事件时间&#xff08;一般流处理都会有两个时间&#xff1a;事件发生的事件&am…...

由播客转向个人定制的音频频道(1)平台搭建

项目的背景 最近开始听喜马拉雅播客的内容&#xff0c;但是发现许多不方便的地方。 休息的时候收听喜马拉雅&#xff0c;但是还需要不断地选择喜马拉雅的内容&#xff0c;比较麻烦&#xff0c;而且黑灯操作反而伤眼睛。 喜马拉雅为代表的播客平台都是VOD 形式的&#xff0…...

[自然语言处理] [AI]深入理解语言与情感分类:从基础到深度学习的进展

语言是人类智能的核心组成部分,具有极高的复杂性和多样性。理解语言,尤其是语言中的隐含部分,向来是人工智能研究的一个巨大挑战。图灵测试本身便是一场关于语言生成与理解的比赛,旨在检验机器是否能够模拟人类的语言能力。随着深度学习的飞速发展,语音识别、情感分析等自…...

【GPTs】Gif-PT:DALL·E制作创意动图与精灵动画

博客主页&#xff1a; [小ᶻZ࿆] 本文专栏: AIGC | GPTs应用实例 文章目录 &#x1f4af;GPTs指令&#x1f4af;前言&#x1f4af;Gif-PT主要功能适用场景优点缺点 &#x1f4af;小结 &#x1f4af;GPTs指令 中文翻译&#xff1a; 使用Dalle生成用户请求的精灵图动画&#…...

云原生周刊:Istio 1.24.0 正式发布

云原生周刊&#xff1a;Istio 1.24.0 正式发布 开源项目推荐 Kopf Kopf 是一个简洁高效的 Python 框架&#xff0c;只需几行代码即可编写 Kubernetes Operator。Kubernetes&#xff08;K8s&#xff09;作为强大的容器编排系统&#xff0c;虽自带命令行工具&#xff08;kubec…...

Linux设置jar包开机启动

操作系统环境&#xff1a;CentOS 7 【需要 root 权限&#xff0c;使用 root 用户进行操作 或 普通用户使用 sudo 进行操作】 一、系统服务的方式 原理&#xff1a;利用系统服务管理应用程序的生命周期&#xff0c; systemctl 为系统服务管理工具 systemctl start applicati…...

计算机视觉和机器人技术中的下一个标记预测与视频扩散相结合

一种新方法可以训练神经网络对损坏的数据进行分类&#xff0c;同时预测下一步操作。 它可以为机器人制定灵活的计划&#xff0c;生成高质量的视频&#xff0c;并帮助人工智能代理导航数字环境。 Diffusion Forcing 方法可以对嘈杂的数据进行分类&#xff0c;并可靠地预测任务的…...

C语言之简单的获取命令行参数和环境变量

C语言之简单的获取命令行参数和环境变量 本人的开发环境为WIN10操作系统用VMWARE虚拟的UBUNTU LINUX 18.04LTS&#xff01;&#xff01;&#xff01; 所有代码的编辑、编译、运行都在虚拟机上操作&#xff0c;初学的朋友要注意这一点&#xff01;&#xff01;&#xff01; 详细…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...