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

【算法与数据结构】动态规划

目录

基本概念

最长递增子序列(中等)

最大子数组和(中等)


基本概念

重叠子问题

一个问题可以被分解为多个子问题,并且这些子问题在求解过程中会被多次重复计算。例如,在计算斐波那契数列时,斐波那契数 F(n) 的计算需要先计算 F(n - 1) 和 F(n - 2),而计算 F(n - 1) 又需要计算 F(n - 2) 和 F(n - 3),这里 F(n - 2) 就是重叠子问题。

最优子结构

问题的最优解可以由子问题的最优解组合而成。也就是说,如果一个问题的最优解包含了子问题的解,那么这些子问题的解本身对于它们各自的子问题来说也必须是最优的。以背包问题为例,要得到能装入背包的最大价值物品组合的最优解,这个最优解取决于装入背包部分容量时选择不同物品所得到的子问题的最优解。

解题步骤

  1. 确定状态:定义问题的状态,状态通常是问题求解过程中的某个中间结果或者某个阶段的情况描述。比如在爬楼梯问题中,状态可以定义为爬到第 n 级楼梯时的不同方法数,这里的 n 就是状态变量。
  2. 建立状态转移方程:根据问题的最优子结构性质,找出状态之间的递推关系,即从一个或多个已知状态推导出另一个状态的方程。在斐波那契数列问题中,状态转移方程就是 F(n) = F(n - 1) + F(n - 2)。
  3. 确定边界条件:明确问题的初始状态或最小子问题的解,这些边界条件是递归求解的基础。对于斐波那契数列,边界条件是 F(0) = 0,F(1) = 1。

最长递增子序列(中等)

nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的

子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

一维动态规划

int[] nums = {10,9,2,5,3,7,101,18};

dp默认都是1

dp[2] = 1

dp[3] = max(dp[3], dp[2]+1) = 2

dp[4] = max(dp[4], dp[2] + 1) =2

dp[5] = max(dp[5], dp[2] + 1) = 2

        max(dp[5], dp[3] + 1) = 3

        max(dp[5], dp[4] + 1) = 3

dp[6] = max(dp[6], dp[2] + 1) = 2

        max(dp[6], dp[3] + 1) = 3

        max(dp[6], dp[4] + 1) = 3

        max(dp[6], dp[5] + 1) = 4

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

最大子数组和(中等)

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]输出:1

示例 3:

输入:nums = [5,4,-1,7,8]输出:23

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}

相关文章:

【算法与数据结构】动态规划

目录 基本概念 最长递增子序列&#xff08;中等&#xff09; 最大子数组和&#xff08;中等&#xff09; 基本概念 重叠子问题 一个问题可以被分解为多个子问题&#xff0c;并且这些子问题在求解过程中会被多次重复计算。例如&#xff0c;在计算斐波那契数列时&#xff0c;…...

DeepSeekMoE:迈向混合专家语言模型的终极专业化

一、结论写在前面 论文提出了MoE语言模型的DeepSeekMoE架构&#xff0c;目的是实现终极的专家专业化(expert specialization)。通过细粒度的专家分割和共享专家隔离&#xff0c;DeepSeekMoE相比主流的MoE架构实现了显著更高的专家专业化和性能。从较小的2B参数规模开始&#x…...

什么是Maxscript?为什么要学习Maxscript?

MAXScript是Autodesk 3ds Max的内置脚本语言,它是一种与3dsMax对话并使3dsMax执行某些操作的编程语言。它是一种脚本语言,这意味着您不需要编译代码即可运行。通过使用一系列基于文本的命令而不是使用UI操作,您可以完成许多使用UI操作无法完成的任务。 Maxscript是一种专有…...

HyperLogLog 近似累计去重技术解析:大数据场景下的高效基数统计

目录 引言 一、HyperLogLog 核心原理 1.1 算法思想 1.2 误差特性 二、SQL 实现详解(PostgreSQL 示例)...

LabVIEW透镜多参数自动检测系统

在现代制造业中&#xff0c;提升产品质量检测的自动化水平是提高生产效率和准确性的关键。本文介绍了一个基于LabVIEW的透镜多参数自动检测系统&#xff0c;该系统能够在单一工位上完成透镜的多项质量参数检测&#xff0c;并实现透镜的自动搬运与分选&#xff0c;极大地提升了检…...

MySQL数据库(二)- SQL

目录 ​编辑 一 DDL (一 数据库操作 1 查询-数据库&#xff08;所有/当前&#xff09; 2 创建-数据库 3 删除-数据库 4 使用-数据库 (二 表操作 1 创建-表结构 2 查询-所有表结构名称 3 查询-表结构内容 4 查询-建表语句 5 添加-字段名数据类型 6 修改-字段数据类…...

【Block总结】HiLo注意力,局部自注意力捕获细粒度的高频信息,通过全局注意力捕获低频信息|即插即用

一、论文信息 标题: Fast Vision Transformers with HiLo AttentionGitHub链接: https://github.com/ziplab/LITv2论文链接: arXiv 二、创新点 HiLo注意力机制: 本文提出了一种新的自注意力机制——HiLo注意力&#xff0c;旨在同时捕捉图像中的高频和低频特征。该机制通过将…...

python 使用Whisper模型进行语音翻译

目录 一、Whisper 是什么? 二、Whisper 的基本命令行用法 三、代码实践 四、是否保留Token标记 五、翻译长度问题 六、性能分析 一、Whisper 是什么? Whisper 是由 OpenAI 开源的一个自动语音识别(Automatic Speech Recognition, ASR)系统。它的主要特点是: 多语言…...

C# Winform enter键怎么去关联button

1.关联按钮上的Key事件按钮上的keypress&#xff0c;keydown&#xff0c;keyup事件随便一个即可private void textBox1_KeyDown(object sender, KeyEventArgs e){if (e.KeyCode Keys.Enter){this.textBox2.Focus();}}2.窗体上的事件private void textBox2_KeyPress(object sen…...

Github 2025-01-30 Go开源项目日报 Top10

根据Github Trendings的统计,今日(2025-01-30统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Go项目10Ollama: 本地大型语言模型设置与运行 创建周期:248 天开发语言:Go协议类型:MIT LicenseStar数量:42421 个Fork数量:2724 次关注人…...

电路研究9.2.6——合宙Air780EP中HTTP——HTTP GET 相关命令使用方法研究

这个也是一种协议类型&#xff1a; 14.16 使用方法举例 根据之前多种类似的协议的相关信息&#xff1a; HTTP/HTTPS&#xff1a;超文本传输协议&#xff08;HTTP&#xff09;用于Web数据的传输&#xff0c;而HTTPS是HTTP的安全版本&#xff0c;使用SSL/TLS进行加密。与FTP相比&…...

Java手写简单Merkle树

Java手写Merkle树代码 package com.blockchain.qgy.component;import com.blockchain.qgy.model.MerkleTreeNode; import com.blockchain.qgy.util.SHAUtil;import java.util.*;public class MerkleTree<T> {//merkle树private List<MerkleTreeNode<T>> lis…...

DeepSeek的使用技巧介绍

DeepSeek是一款由杭州深度求索人工智能技术有限公司开发的AI工具&#xff0c;结合了自然语言处理和深度学习技术&#xff0c;能够完成多种任务&#xff0c;如知识问答、数据分析、文案创作、代码开发等。以下将从使用技巧、核心功能及注意事项等方面详细介绍DeepSeek的使用方法…...

19 压测和常用的接口优化方案

高并发的平台应用&#xff0c;项目上线前离不开一个重要步骤就是压测&#xff0c;压测对于编码中的资源是否问题的排查&#xff0c;性能的调优都是离不开的。测试还要做测试报告&#xff0c;出具了测试报告给到运维团队才能上线。 压测的测试报告主要有以下几个方面:1.响应时间…...

AI应用部署——streamlit

如何把项目部署到一个具有公网ip地址的服务器上&#xff0c;让他人看到&#xff1f; 可以利用 streamlit 的社区云免费部署 1、生成requirements.txt文件 终端输入pip freeze > requirements.txt即可 requirements.txt里既包括自己安装过的库&#xff0c;也包括这些库的…...

NLP自然语言处理通识

目录 ELMO 一、ELMo的核心设计理念 1. 静态词向量的局限性 2. 动态上下文嵌入的核心思想 3. 层次化特征提取 二、ELMo的模型结构与技术逻辑 1. 双向语言模型&#xff08;BiLM&#xff09; 2. 多层LSTM的层次化表示 三、ELMo的运行过程 1. 预训练阶段 2. 下游任务微调 四、ELMo的…...

C++ 6

C构造函数有几种&#xff0c;分别什么作用 在C中&#xff0c;构造函数有几种不同的类型&#xff0c;每种都有其特定的作用&#xff1a; 默认构造函数&#xff1a;没有参数的构造函数&#xff0c;用于创建对象的默认实例。参数化构造函数&#xff1a;带参数的构造函数&#xf…...

使用QSqlQueryModel创建交替背景色的表格模型

class UserModel(QSqlQueryModel):def __init__(self):super().__init__()self._query "SELECT name, age FROM users"self.refresh()def refresh(self):self.setQuery(self._query)# 重新定义data()方法def data(self, index, role): if role Qt.BackgroundRole…...

jinfo命令详解

jinfo [option]option 有以下这些选项参数 -flag : 打印 指定名称的 jvm 参数值&#xff1b;-flag [|-] : 启动或禁用指定名称的 jvm参数&#xff1b;-flag : 设置指定名称的 jvm 参数值&#xff1b;-sysprops: 打印 java 系统属性-h | -help: 打印 jinfo 命令帮助信息 1&…...

如何在 ACP 中建模复合罐

概括 本篇博文介绍了 ANSYS Composite PrepPost (ACP) 缠绕向导。此工具允许仅使用几个条目自动定义高压罐中常见的悬垂复合结构。 ACP 绕线向导 将必要的信息输入到绕组向导中。重要的是要注意“参考半径”&#xff0c;它代表圆柱截面的半径&#xff0c;以及“轴向”&#x…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...