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

相关文章

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

PostgreSQL 序列(Sequence) 与 Oracle 序列对比差异分析

《PostgreSQL序列(Sequence)与Oracle序列对比差异分析》PostgreSQL和Oracle都提供了序列(Sequence)功能,但在实现细节和使用方式上存在一些重要差异,... 目录PostgreSQL 序列(Sequence) 与 oracle 序列对比一 基本语法对比1.1 创建序

Linux区分SSD和机械硬盘的方法总结

《Linux区分SSD和机械硬盘的方法总结》在Linux系统管理中,了解存储设备的类型和特性是至关重要的,不同的存储介质(如固态硬盘SSD和机械硬盘HDD)在性能、可靠性和适用场景上有着显著差异,本文... 目录一、lsblk 命令简介基本用法二、识别磁盘类型的关键参数:ROTA查询 ROTA 参数ROTA

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)