LIS(最长递增子序列)和LCS(最长公共子序列)的总结

2024-08-24 04:08

本文主要是介绍LIS(最长递增子序列)和LCS(最长公共子序列)的总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LIS(最长递增子序列)和LCS(最长公共子序列)的总结

最长公共子序列(LCS):O(n^2)

两个for循环让两个字符串按位的匹配:i in range(1, len1) j in range(1, len2)
s1[i - 1] == s2[j - 1], dp[i][j] = dp[i - 1][j -1] + 1;
s1[i - 1] != s2[j - 1], dp[i][j] = max (dp[i - 1][j], dp[i][j - 1]);
初始化:dp[i][0] = dp[0][j] = 0;

伪代码:
    dp[maxn1][maxn2];s1[maxn1],s2[maxn2];p[maxn1][maxn2][2];//initfor i in range(0, len1):dp[i][0] = 0;else:;for i in range(0, len2):dp[0][i] = 0;else:;for i in range(1, len1):for j in range(1, len2):if s1[i] == s2[j]:dp[i][j] = dp[i - 1][j - 1] + 1;p[i][j][0] = i - 1;p[i][j][1] = j - 1;else:if dp[i - 1][j] > dp[i][j - 1]:dp[i][j] = dp[i - 1][j];p[i][j][0] = i - 1;p[i][j][1] = j;else:dp[i][j] = dp[i][j - 1];p[i][j][0] = i;p[i][j][1] = j - 1;else:;else:;return dp[len1][len2];//path 非递归function print_path(len1, len2):if (dp[len1][len2] == 0)return;printf_path(p[len1][len2][0], p[len1][len2][1]);if s1[len1] == s2[len2]:printf:s1[len1];end function;

题目:UVA - 531Compromise UVA - 10066The Twin Towers UVA - 10192Vacation
uva10405 - Longest Common Subsequence

最长递增子序列(LIS):O(n^2)

从左到右的求前i长度的序列的最长递增子序列的长度,状态转移方程:
dp[i] = Max(dp[j] + 1);i in range(1, len); j in range(1, i - 1);

伪代码
    s[maxn],dp[maxn];for i in range(1, len):dp[i] = 1;int maxlen = 1;for i in range(2, len):for j range(1, i - 1):if s[i] > s[j]:dp[i] = Max(dp[i], dp[j] + 1);else:maxlen = max(maxlen, dp[i]);else:;return maxlen;//path递归function print_path(maxlen):if maxlen == 0:return;for i in range(1, len):if dp[i] == maxlen:print_path(maxlen - 1);printf:s[i];end function;

题目: UVA - 10599Robots(II)

最长递增子序列O(n * logn)

还是从左往右的求前i长度的序列的最长递增子序列长度,但是再确定dp[j]最大值的时候还要用一层循环来查找,这样比较低效.如果把前面的i长度序列出现的最长递增子序列储存起来,那么查找的时候用二分就可以做到O(logn)的复杂度。
用一个LIS数组来储蓄前i序列的最长递增子序列,查找第i个数字的时候,如果num[i] > LIS[top], 那么LIS[++top] = num[i]; dp[i] = top;如果num[i] == LIS[top],那么dp[i] = top; 如果num[i] < LIS[top], 那么二分查找到某个等于或者大于num[i]的最接近的值的位置(第k个),dp[i] = k - 1; LIS[k] = num[i];

题目:UVA - 10534Wavio Sequence

伪代码
    dp[maxn], LIS[maxn], s[maxn];top = 0;LIS[top++] = s[1];int maxlen = 1;for i in range(2, len):if s[i] > LIS[top]:LIS[++top] = s[i];dp[i] = top + 1;else if s[i] == LIS[top]:dp[i] = top + 1;else:k = lower_bound(LIS.begin(), LIS.end(), s[i]) - LIS.beign();LIS[k] = s[i];dp[i] = k + 1;maxlen = max(maxlen, dp[i]);else:;return maxlen;
最长公共子序列O(n * logn)

要求串本身不会出现相同的数字或是字母。通过对第一个字符串进行映射(递增的顺序),然后第二个字符串依照上面的第一个字符串等价映射,这样就把问题从LCS转化成LIS。例如:
串1: 2 4 3 5 6
映射:1 2 3 4 5
串2: 3 2 6 8 10
等价映射:3 1 5 0 0

题目:uva10635Prince and Princess


这篇关于LIS(最长递增子序列)和LCS(最长公共子序列)的总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101399

相关文章

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

Python依赖库的几种离线安装方法总结

《Python依赖库的几种离线安装方法总结》:本文主要介绍如何在Python中使用pip工具进行依赖库的安装和管理,包括如何导出和导入依赖包列表、如何下载和安装单个或多个库包及其依赖,以及如何指定... 目录前言一、如何copy一个python环境二、如何下载一个包及其依赖并安装三、如何导出requirem

Rust格式化输出方式总结

《Rust格式化输出方式总结》Rust提供了强大的格式化输出功能,通过std::fmt模块和相关的宏来实现,主要的输出宏包括println!和format!,它们支持多种格式化占位符,如{}、{:?}... 目录Rust格式化输出方式基本的格式化输出格式化占位符Format 特性总结Rust格式化输出方式

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

Python中连接不同数据库的方法总结

《Python中连接不同数据库的方法总结》在数据驱动的现代应用开发中,Python凭借其丰富的库和强大的生态系统,成为连接各种数据库的理想编程语言,下面我们就来看看如何使用Python实现连接常用的几... 目录一、连接mysql数据库二、连接PostgreSQL数据库三、连接SQLite数据库四、连接Mo

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》:本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push