CSP-动态规划-最长公共子序列(LCS)

一、动态规划

动态规划(Dynamic Programming,简称DP)主要用于求解可以被分解为相似子问题的复杂问题,特别是在优化问题上表现出色,如最短路径、最大子数组和、编辑距离等。动态规划的核心思想是将原问题分解为较小的子问题,通过解决这些子问题,并将结果存储起来(通常是在一个数组或者哈希表中),以避免重复计算,从而提高效率。

动态规划问题的解决通常遵循以下几个步骤:

  1. 暴力穷举所有答案。
  2. 画出递归树,尝试编写递归函数求解。
  3. 若遍历中存在大量重复计算,使用哈希表缓存数据,之后遍历到相同节点就直接查表。
  4. 表示整个计算过程,观察公式求解顺序,改写成更加高效的迭代形式。

二、动态规划的例子

1.斐波那契数列

2.背包问题

3. 最长公共子序列(LCS)

  • 给定一个无序数组nums=[1,5,2,4,3],找出其中最长的递增的子序列,比如1-2-41-2-3。将问题简化,要求算法只返回最长序列的长度(3)

(1) 暴力枚举

  • 把每个子序列都“找个遍”,并且在遍历过程中实时记录当前子序列的长度
    图片描述

(2) 递归解决方案

  1. 递归函数 L:用于计算以特定元素结尾的最长递增子序列的长度;

    • 基础情形:如果当前考虑的元素是数组的最后一个元素,那么以它结尾的最长递增子序列的长度为 1,因为它自身就构成了一个长度为 1 的递增子序列。
    • 递归步骤:对于非最后一个元素,函数会遍历当前元素之后的所有元素,寻找一个值比当前元素大的元素,这意味着可以形成一个递增的序列。对于每一个这样的元素,函数会递归地计算以那个元素为结尾的最长递增子序列的长度,并将其与当前最大长度比较,更新当前最大长度。这个过程会重复直到数组结束。
    • 返回值:函数最终返回以当前元素结尾的最长递增子序列的长度。
  2. 函数 lengthOfLIS:作用是找到整个数组的最长递增子序列的长度。

    • 遍历给定数组的每个元素,对每个元素调用递归函数 L,计算以该元素为结尾的最长递增子序列的长度。
    • 比较并更新 max_len 为当前找到的最长递增子序列的长度。
    • 遍历完成后,返回 max_len 作为最终结果。
#include <iostream>
#include <vector>
using namespace std;// 计算以 nums[i] 结尾的最长递增子序列的长度
int L(const vector<int>& nums, int i) {if (i == nums.size() - 1) { // 如果是最后一个元素return 1; // 最长递增子序列长度为1}int max_len = 1; // 初始化最大长度为1for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] > nums[i]) { // 如果找到一个递增的元素// 递归计算以 nums[j] 结尾的最长递增子序列长度,并加1(加上nums[i])// 然后与当前的最大长度取较大值max_len = max(max_len, L(nums, j) + 1);}}return max_len; // 返回以 nums[i] 结尾的最长递增子序列的长度
}// 计算给定序列的最长递增子序列长度
int lengthOfLIS(const vector<int>& nums) {int max_len = 0; // 初始化全局最大长度为0for (int i = 0; i < nums.size(); ++i) {// 遍历每个元素,计算以每个元素为起点的最长递增子序列的长度// 然后取所有长度中的最大值max_len = max(max_len, L(nums, i));}return max_len; // 返回最长递增子序列的长度
}int main() {vector<int> nums = {1, 5, 2, 4, 3}; cout << lengthOfLIS(nums) << endl; return 0;
}

(3) 递归的问题

  • 直接递归的方法在时间复杂度上是非常高的,因为它会重复计算很多子问题的解。
  • 比如,在遍历子序列1-2-4时就已经计算过“L(4)”,后面遍历1,4时又重复计算了一次。

(4) 递归的优化:动态规划

  • 为了避免递归中出现的重复计算,可以将第一次计算时的结果保存,之后再当遍历到相同的节点我们就不在需要重复计算,直接返回之前的结果即可。

  • 在这个版本中,L 函数中添加了一个 unordered_map (哈希表)类型的备忘录 memo,用于存储已经计算过的子问题的解。在递归的过程中,先检查备忘录是否已经包含了当前子问题的解,如果有则直接返回保存的结果,避免了重复计算。这样能够显著提高程序的性能。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;// 使用备忘录的递归方式计算以 nums[i] 结尾的最长递增子序列的长度
int L(const vector<int>& nums, int i, unordered_map<int, int>& memo) {if (i == nums.size() - 1) {return 1;}if (memo.find(i) != memo.end()) {return memo[i]; // 如果已经计算过,直接返回保存的结果}int max_len = 1;for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] > nums[i]) {max_len = max(max_len, L(nums, j, memo) + 1);}}memo[i] = max_len; // 将结果保存到备忘录中return max_len;
}// 计算给定序列的最长递增子序列长度
int lengthOfLIS(const vector<int>& nums) {int max_len = 0;unordered_map<int, int> memo; // 使用unordered_map作为备忘录for (int i = 0; i < nums.size(); ++i) {max_len = max(max_len, L(nums, i, memo));}return max_len;
}int main() {vector<int> nums = {1, 5, 2, 4, 3};cout << lengthOfLIS(nums) << endl;return 0;
}

(5) 递归转非递归

  • 从后往前依次计算,即可推算出所有答案(数学归纳)
    图片描述

  • dp 数组:用于存储以每个元素结尾的最长递增子序列的长度。

  • 双重循环:外层循环遍历每个元素,内层循环遍历当前元素之前的元素,更新以当前元素结尾的最长递增子序列的长度。

  • max_element 函数:返回 dp 数组中的最大值,即整个数组中最长递增子序列的长度。

#include <iostream>
#include <vector>
using namespace std;int lengthOfLIS(const vector<int>& nums) {int n = nums.size();if (n == 0) return 0; // 处理空数组的情况vector<int> dp(n, 1); // 初始化dp数组,每个元素代表以对应位置元素结尾的最长递增子序列的长度for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长递增子序列长度}}}return *max_element(dp.begin(), dp.end()); // 返回dp数组中的最大值,即最长递增子序列的长度
}int main() {vector<int> nums = {1, 5, 2, 4, 3}; // 定义一个序列cout << lengthOfLIS(nums) << endl; // 输出最长递增子序列的长度return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/258410.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python第十七章(继承)

继承&#xff1a;子类继承父类的所有方法和属性 一。单继承&#xff1a;一个子类继承一个父类 注释&#xff1a;B是子类&#xff0c;继承了A的函数方法&#xff0c;当调用B时候&#xff0c;会同时使用A中的全部方法&#xff0c;object类是顶级类或者基类&#xff0c;其他子类叫…

机器学习入门--门控循环单元(GRU)原理与实践

GRU模型 随着深度学习领域的快速发展&#xff0c;循环神经网络&#xff08;RNN&#xff09;已成为自然语言处理&#xff08;NLP&#xff09;等领域中常用的模型之一。但是&#xff0c;在RNN中&#xff0c;如果时间步数较大&#xff0c;会导致梯度消失或爆炸的问题&#xff0c;…

《山雨欲来-知道创宇 2023 年度 APT 威胁分析总结报告》

下载链接: https://pan.baidu.com/s/1eaIOyTk12d9mcuqDGzMYYQ?pwdzdcy 提取码: zdcy

【sgCreateTableColumn】自定义小工具:敏捷开发→自动化生成表格列html代码(表格列生成工具)[基于el-table-column]

源码 <template><!-- 前往https://blog.csdn.net/qq_37860634/article/details/136126479 查看使用说明 --><div :class"$options.name"><div class"sg-head">表格列生成工具</div><div class"sg-container"…

python in Vscode

背景 对于后端的语言选择&#xff1a; python&#xff0c;java&#xff0c;JavaScript备选。 选择Python 原因&#xff1a;可能是非IT专业的人中&#xff0c;会Python的人比较多。 目的 之前使用的IDE是VSCODE&#xff0c;在WSL的环境下使用。现在需要在在WSL的VSCODE下使…

使用Properties类读取配置文件

读取配置文件 使用Properties类读取配置文件。 Properties类本质上是个hashmap 常用方法 getProperty ( String key)&#xff1a; 用指定的键在此属性列表中搜索属性。也就是通过参数 key &#xff0c;得到 key 所对应的 value。load ( InputStream inStream)&#xff1a; 从输…

字符串拼接 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 200分 题解&#xff1a; Java / Python / C 题目描述 给定 M 个字符( a-z ) &#xff0c;从中取出任意字符(每个字符只能用一次)拼接成长度为 N 的字符串&#xff0c;要求相同的字符不能相邻。 计算出给定的字符列表…

Maui blazor ios 按设备类型设置是否启用safeArea

需求&#xff0c;新做了个app&#xff0c; 使用的是maui blazor技术&#xff0c;里面用了渐变背景&#xff0c;在默认启用SafeArea情况下&#xff0c;底部背景很突兀 由于现版本maui在SafeArea有点bug&#xff0c;官方教程的<ContentPage SafeAreafalse不生效&#xff0c;于…

【机器学习】数据清洗之识别重复点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

STM32 HAL库 STM32CubeMX -- IWDG(独立看门狗)

STM32 HAL库 STM32CubeMX -- IWDG 一、IWDG简介二、独立看门狗的工作原理三、驱动函数初始化函数HAL IWDG Init()初始化函数HAL IWDG Init()其他宏函数 四、超时时间计算第一种办法第二种办法&#xff08;推荐&#xff09; 一、IWDG简介 看门狗(Watchdog)就是MCU上的一种特殊的…

SORA:OpenAI最新文本驱动视频生成大模型技术报告解读

Video generation models as world simulators&#xff1a;作为世界模拟器的视频生成模型 1、概览2、Turning visual data into patches&#xff1a;将视觉数据转换为补丁3、Video compression network&#xff1a;视频压缩网络4、Spacetime Latent Patches&#xff1a;时空潜在…

SAP PP学习笔记- 豆知识02 - 品目要谁来维护?怎么决定更不更新品目的数量金额?

其实都是在品目类型的Customize中设定的。 咱们这里简单试着说一下什么场景使用。 1&#xff0c;SAP中品目有很多View&#xff0c;都要由哪些部门来维护呢&#xff1f; 其实就是谁用谁维护呗。 在新建一个品目的时候&#xff0c;品目Type本身就决定了该品目要由哪些部门来维…

【STM32 CubeMX】串口编程DMA

文章目录 前言一、DMA方式1.1 DMA是什么1.2 CubeMX配置DMA1.3 DMA方式函数使用DMA的发送接收函数 总结 前言 在嵌入式系统中&#xff0c;串口通信是一项至关重要的功能&#xff0c;它允许单片机与外部设备进行数据交换&#xff0c;如传感器、显示器或其他设备。然而&#xff0…

【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

二叉树 一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 性质 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2i−1, i ≥ 1 i \geq 1 i≥1 每层最大结点可以对应完美二叉树&#xff08;…

阿里云服务器租用收费标准价格表(2024年更新)

2024年最新阿里云服务器租用费用优惠价格表&#xff0c;轻量2核2G3M带宽轻量服务器一年61元&#xff0c;折合5元1个月&#xff0c;新老用户同享99元一年服务器&#xff0c;2核4G5M服务器ECS优惠价199元一年&#xff0c;2核4G4M轻量服务器165元一年&#xff0c;2核4G服务器30元3…

Gitee入门之工具的安装

一、gitee是什么&#xff1f; Gitee&#xff08;码云&#xff09;是由开源中国社区在2013年推出的一个基于Git的代码托管平台&#xff0c;它提供中国本土化的代码托管服务。它旨在为个人、团队和企业提供稳定、高效、安全的云端软件开发协作平台&#xff0c;具备代码质量分析、…

React18原理: 核心包结构与两大工作循环

React核心包结构 1 ) react react基础包&#xff0c;只提供定义 react组件(ReactElement)的必要函数一般来说需要和渲染器(react-dom,react-native)一同使用在编写react应用的代码时, 大部分都是调用此包的api比如, 我们定义组件的时候&#xff0c;就是它提供的class Demo ext…

springboot198基于springboot的智能家居系统

基于Springboot的智能家居系统 **[摘要]**社会和科技的不断进步带来更便利的生活&#xff0c;计算机技术也越来越平民化。二十一世纪是数据时代&#xff0c;各种信息经过统计分析都可以得到想要的结果&#xff0c;所以也可以更好的为人们工作、生活服务。智能家居是家庭的重要…

【排序算法】C语言排序(桶排序,冒泡排序,选择排序,插入排序,快速排序)

目录 什么是排序&#xff1f;1、桶排序 概念思路demo运行效果 2、冒泡排序 动图演示概念思路demo运行效果 3、选择排序 动图演示概念思路demo运行结果 4、插入排序 动图演示概念思路demo运行效果 5、快速排序 动图演示概念思路demo运行结果 什么是排序&#xff1f; 排序&…

“分布式透明化”在杭州银行核心系统上线之思考

导读 随着金融行业数字化转型的需求&#xff0c;银行核心系统的升级改造成为重要议题。杭州银行成功上线以 TiDB 为底层数据库的新一代核心业务系统&#xff0c;该实践采用应用与基础设施解耦、分布式透明化的设计开发理念&#xff0c;推动银行核心系统的整体升级。 本文聚焦…