算法27：最长回文子序列长度——范围模型

news/2024/10/19 9:36:25/

目录

题目：

样本模型：

递归版本的范围模型

分析过程

动态规划版本

优化动态规划：

题目：

给定一个字符串str，返回这个字符串的最长回文子序列长度

比如 str = “a12b3c43def2ghi1kpm” * 最长回文子序列是“1234321”或者“123c321”，返回长度7

这一题使用样本模型，也可以解决，只需要生成一个逆序字符串就可以了。因为回文子序列，逆序以后，回文子序列依旧保持原来的顺序结构。

样本模型：

package code03.动态规划_07;/*** 给定一个字符串str，返回这个字符串的最长回文子序列长度* 比如 ： str = “a12b3c43def2ghi1kpm”* 最长回文子序列是“1234321”或者“123c321”，返回长度7** https://leetcode.com/problems/longest-palindromic-subsequence/*/
public class PalindromeSubsequence_05
{public static int longestPalindromeSubseq(String str) {if (str == null || str.isEmpty()) {return 0;}char[] s1 = str.toCharArray();char[] s2 = new char[s1.length];int position = 0;//生成逆序for (int i = s1.length-1; i >=0; i--) {s2[position++] = s1[i];}//以s1做行，s2做列int[][] dp = new int[ s1.length][s2.length];int index1 = s1.length - 1;int index2 = s2.length - 1;//根据递归   if (index1 == 0 && index2 == 0)  而来dp[0][0] = s1[0] == s2[0] ? 1 : 0;//根据递归  else if (index1 == 0)  而来, 此处代表先处理 第一行的所有列for (int i = 1; i <= index2; i++) {dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i-1];}//根据递归  else if (index2 == 0)  而来, 此处代表先处理 第一列的所有行for (int j = 1; j <= index1; j++) {dp[j][0] = s1[j] == s2[0] ? 1 : dp[j-1][0];}//通用case  根据递归中最后一个else而来for (int row = 1; row <= index1; row++) {for (int col = 1; col <= index2; col++) {//根据 int p1 =  process(s1, s2, index1, index2-1) 改写int p1 = dp[row][col - 1];//根据 int p2 =  process(s1, s2, index1-1, index2) 改写int p2 = dp[row -1][col];//int p3 = s1[index1] == s2[index2] ? (process(s1, s2, index1-1, index2-1) + 1) : 0;int p3 = s1[row] == s2[col] ? (dp[row -1][col -1] + 1) : 0;dp[row][col] = Math.max(p1, Math.max(p2, p3));}}//返回值对应递归中的下标return dp[index1][index2];}
}

样本模型，在上一篇已经详细的说过了，具体推导过程可以参照 算法27：最长公共子序列——样本模型（4）_chen_yao_kerr的博客-CSDN博客

样本模型，都是以样本的最后一个元素为基础进行讨论分析的。

而范围模型，则是以样本数据的  开头  和  结尾   进行讨论的。

递归版本的范围模型

package code03.动态规划_07;/*** 给定一个字符串str，返回这个字符串的最长回文子序列长度* 比如 ： str = “a12b3c43def2ghi1kpm”* 最长回文子序列是“1234321”或者“123c321”，返回长度7** https://leetcode.com/problems/longest-palindromic-subsequence/*/
public class PalindromeSubsequence_05_opt1
{public static int longestPalindromeSubseq(String str){if (str == null || str.isEmpty()) {return 0;}return process(str.toCharArray(), 0, str.length() -1);}//范围模型，需要讨论样本数据的开头和结尾public static int process(char[] str, int left, int right){//如果长度为1,也就是说字符串只有一个字符if (left == right) {return 1;}//字符串只有2个元素. 如果第一个元素和第二个元素相同，则说明回文//长度为2. 否则，最长子回文只有1，因为我们默认的子序列回文长度就是为1.if (left == right -1) {return str[left] == str[right] ? 2 : 1;}/*** 最长回文子序列, 有可能出现以下情况* 1. 包含结尾，不包含开头* 2. 包含开头，不包含结尾* 3. 既不包含开头，也不包含结尾* 4. 既包含开头，也包含结尾*///包含结尾，不包含开头int p1 = process(str, left + 1, right);//包含开头，不包含结尾int p2 = process(str, left, right - 1);//既不包含开头，也不包含结尾int p3 = process(str, left + 1, right - 1);//既包含开头，也包含结尾int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));//也可以改写成 int p4 = str[left] != str[right] ? 0 : (2 + p3);return Math.max(Math.max(p1, p2), Math.max(p3, p4));}public static void main(String[] args) {System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));}
}

分析过程

1. 假设字符串为 a12a21b，我们知道最长回文子序列为12a21, 那么它的长度就是5.

2. 构建二维数组.  行和列都是数组的下标。递归的传入参数 0 和  str.length() -1，分别代表数组的左边开始位置和右边开始位置。将left作为行，right作为列，那么可以推导出如下的表格信息

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)
1(1)x
2(2)xx
3(a)xxx
4(2)xxxx
5(1)xxxxx
6(b)xxxxxx

3. 根据递归的

if (left == right) {return 1;
}

可以推算出对角线全部为 1.

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)1
1(1)x1
2(2)xx1
3(a)xxx1
4(2)xxxx1
5(1)xxxxx1
6(b)xxxxxx1

4. 根据递归

if (left == right -1) {return str[left] == str[right] ? 2 : 1;
}

可以推算出：

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)11
1(1)x11
2(2)xx11
3(a)xxx11
4(2)xxxx11
5(1)xxxxx11
6(b)xxxxxx1

5.  核心推算过程

//包含结尾，不包含开头。我们知道（left，right）依赖（left+1, right）,即下一行
int p1 = process(str, left + 1, right);
//包含开头，不包含结尾. 我们知道（left，right）依赖（left, right -1）即前一列
int p2 = process(str, left, right - 1);
//既不包含开头，也不包含结尾。我们知道（left，right）依赖（left+1, right -1）即前一列的下一行
int p3 = process(str, left + 1, right - 1);
//既包含开头，也包含结尾。我们知道（left，right）依赖（left+1, right -1）即前一列的下一行
int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));

也就是说（left，right）依赖当前行的前一列、下一行的当前列 和 前一行的前一列/

也就是说想要知道dp[4][6]的值，必须先知道dp[4][5]  dp[5][6] 和 dp[5][5] 的值。而这几个值已经推出来了，那就拿到最大值 1.

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)11
1(1)x11
2(2)xx11
3(a)xxx11
4(2)xxxx11
5(1)xxxxx11
6(b)xxxxxx1

 还是按照以上的信息，根据前一列、下一行的当前列 以及前一行的前一列可以推算出结果。

以dp[3][6]为例子。 dp[3][5]为3， dp[4][6]为3，dp[4][5]为1. 并且字符串下标3的值为a，6的位置为b， a!=b, 因此维持最大值3. 如果相等，那就额外再加 2。

                                                依次类推，第一个变化的位置为dp[2][4]

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)111
1(1)x111
2(2)xx113
3(a)xxx111
4(2)xxxx111
5(1)xxxxx11
6(b)xxxxxx1

                                        依次类推，得到完整的表格信息

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)1113355
1(1)x111355
2(2)xx11333
3(a)xxx1111
4(2)xxxx111
5(1)xxxxx11
6(b)xxxxxx1

动态规划版本

package code03.动态规划_07;/*** 给定一个字符串str，返回这个字符串的最长回文子序列长度* 比如 ： str = “a12b3c43def2ghi1kpm”* 最长回文子序列是“1234321”或者“123c321”，返回长度7** https://leetcode.com/problems/longest-palindromic-subsequence/*/
public class PalindromeSubsequence_05_opt2
{public static int longestPalindromeSubseq(String str){if (str == null || str.isEmpty()) {return 0;}//构造一个 n * n的矩阵char[] s = str.toCharArray();int[][] dp = new int[s.length][s.length];//最后一行的最后一列比较特殊，会出现数组越界，需要单独设置dp[s.length-1][s.length-1] = 1;for (int i = 0; i < s.length - 1 ; i++) {//根据递归  if (left == right) 得到对角线全部为1dp[i][i] = 1;//根据递归 if (left == right -1) { 得到对角线的后一列值dp[i][i+1] = s[i] == s[i+1] ? 2 : 1;}//由于倒数第一、第二行已经推算出来了，因此从倒数第三行开始推算for (int row = s.length - 3; row >= 0; row--){//从倒数第一行开始推算。并且列需要随着行变化而变化for (int col = row + 2; col < s.length ; col++){//包含开头，不包含结尾int p1 = dp[row + 1][col];//包含结尾，不包含开头int p2 = dp[row][col - 1];//既不包含开头，也不包含结尾int p3 =  dp[row + 1][col - 1];//既包含开头，也包含结尾int p4 = s[row] != s[col] ? 0 : (2 + dp[row + 1][col - 1]);dp[row][col] = Math.max(Math.max(p1, p2), Math.max(p3, p4));}}return dp[0][s.length-1];}public static void main(String[] args) {System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));}
}

优化动态规划：

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)111
1(1)x111
2(2)xx113
3(a)xxx111
4(2)xxxx111
5(1)xxxxx11
6(b)xxxxxx1

dp[2][4]位置是第一次发生变化的。下一轮，我们会推算出如下结果：

0(a)1(1)2(2)3(a)4(2)5(1)6(b)
0(a)1113
1(1)x1113
2(2)xx1133
3(a)xxx1111
4(2)xxxx111
5(1)xxxxx11
6(b)xxxxxx1

而dp[1][5]位置依赖 dp[1][4] 、 dp[2][5] 和 dp[2][4]. 

但是dp[1][4] 和  [2][5]已经推算出来了，他们都依赖dp[2][4]。

也就是说dp[1][4] 和  [2][5]至少都是大于或等于dp[2][4位置的数据的，

我们的逻辑是获取到最大值，既然能够拿到大于等于它的值，那么dp[1][5]直接依赖dp[1][4] 和  [2][5]就可以了，没必要再去依赖较小的dp[2][4]值了。

因此，单独的依赖左下方，即p3就可以省略

递归优化：

package code03.动态规划_07;/*** 给定一个字符串str，返回这个字符串的最长回文子序列长度* 比如 ： str = “a12b3c43def2ghi1kpm”* 最长回文子序列是“1234321”或者“123c321”，返回长度7** https://leetcode.com/problems/longest-palindromic-subsequence/*/
public class PalindromeSubsequence_05_opt1
{public static int longestPalindromeSubseq(String str){if (str == null || str.isEmpty()) {return 0;}return process(str.toCharArray(), 0, str.length() -1);}//范围模型，需要讨论样本数据的开头和结尾public static int process(char[] str, int left, int right){//如果长度为1,也就是说字符串只有一个字符if (left == right) {return 1;}//字符串只有2个元素. 如果第一个元素和第二个元素相同，则说明回文//长度为2. 否则，最长子回文只有1，因为我们默认的子序列回文长度就是为1.if (left == right -1) {return str[left] == str[right] ? 2 : 1;}/*** 最长回文子序列, 有可能出现以下情况* 1. 包含结尾，不包含开头* 2. 包含开头，不包含结尾* 3. 既不包含开头，也不包含结尾* 4. 既包含开头，也包含结尾*///包含结尾，不包含开头int p1 = process(str, left + 1, right);//包含开头，不包含结尾int p2 = process(str, left, right - 1);//既不包含开头，也不包含结尾//int p3 = process(str, left + 1, right - 1);//既包含开头，也包含结尾int p4 = str[left] != str[right] ? 0 : (2 + process(str, left + 1, right - 1));return Math.max(Math.max(p1, p2), p4);}public static void main(String[] args) {System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));}
}

动态规划版本优化：

package code03.动态规划_07;/*** 给定一个字符串str，返回这个字符串的最长回文子序列长度* 比如 ： str = “a12b3c43def2ghi1kpm”* 最长回文子序列是“1234321”或者“123c321”，返回长度7** https://leetcode.com/problems/longest-palindromic-subsequence/*/
public class PalindromeSubsequence_05_opt2
{public static int longestPalindromeSubseq(String str){if (str == null || str.isEmpty()) {return 0;}//构造一个 n * n的矩阵char[] s = str.toCharArray();int[][] dp = new int[s.length][s.length];//最后一行的最后一列比较特殊，会出现数组越界，需要单独设置dp[s.length-1][s.length-1] = 1;for (int i = 0; i < s.length - 1 ; i++) {//根据递归  if (left == right) 得到对角线全部为1dp[i][i] = 1;//根据递归 if (left == right -1) { 得到对角线的后一列值dp[i][i+1] = s[i] == s[i+1] ? 2 : 1;}//由于倒数第一、第二行已经推算出来了，因此从倒数第三行开始推算for (int row = s.length - 3; row >= 0; row--){//从倒数第一行开始推算。并且列需要随着行变化而变化for (int col = row + 2; col < s.length ; col++){/*    //包含开头，不包含结尾int p1 = dp[row + 1][col];//包含结尾，不包含开头int p2 = dp[row][col - 1];//既不包含开头，也不包含结尾int p3 =  dp[row + 1][col - 1];//既包含开头，也包含结尾int p4 = s[row] != s[col] ? 0 : (2 + dp[row + 1][col - 1]);dp[row][col] = Math.max(Math.max(p1, p2), Math.max(p3, p4));*///包含开头，不包含结尾int p1 = dp[row + 1][col];//包含结尾，不包含开头int p2 = dp[row][col - 1];dp[row][col] = Math.max(p1, p2);if (s[row] == s[col] ) {dp[row][col] = Math.max(dp[row][col], 2 + dp[row + 1][col - 1]);}}}return dp[0][s.length-1];}public static void main(String[] args) {System.out.println(longestPalindromeSubseq("a12b3c43def2ghi1kpm"));}
}


http://www.ppmy.cn/news/107145.html

相关文章

孪生诱捕网络在欺骗防御领域的应用

孪生诱捕网络在欺骗防御领域的应用

随着以数字化、网络化和智能化为特征的信息化浪潮的蓬勃兴起&#xff0c;信息已经成为重要的战略资源与重要生产要素&#xff0c;在国家的发展和人们的生产生活中起到至关重要的作用。信息化在给人们带来便利的同时&#xff0c;网络信息安全问题也日益凸显。经过多年的网络安全…
阅读更多...
C++ new delete

C++ new delete

可执行程序(进程) 的虚拟地址空间: 内核: 操作系统 栈区:函数的形参&#xff0c;非静态的局部变量&#xff0c;函数现场保护数据等等&#xff0c;栈是向下增长的。 共享库的内存映射区域:用于装载一个共享的动态内存库。用户可使用系统接口创建共享内存&#xff0c;做进程间通…
阅读更多...
CSDN上海城市开发者社区线下活动纪实

CSDN上海城市开发者社区线下活动纪实

引言 5月27号中午&#xff0c;很高兴能和现CSDN副总裁、前微软 Azure 工程团队首席研发经理、技术畅销书《编程之美》及《构建之法》的作者邹欣邹老师&#xff0c;以及CSDN的 “上海城市开发者社区” 的部分成员齐聚一堂&#xff0c;参加CSDN上海城市开发者社区自5月初成立以来…
阅读更多...
【SQL Server】数据库开发指南（七）MS-SQL存储过程全面解析：种类、优点和创建方法详解

【SQL Server】数据库开发指南（七）MS-SQL存储过程全面解析：种类、优点和创建方法详解

本系列博文还在更新中&#xff0c;收录在专栏&#xff1a;#MS-SQL Server 专栏中。 本系列文章列表如下&#xff1a; 【SQL Server】 Linux 运维下对 SQL Server 进行安装、升级、回滚、卸载操作 【SQL Server】数据库开发指南&#xff08;一&#xff09;数据库设计 【SQL Se…
阅读更多...
Web前端笔记|表格、＜div＞标签、＜span＞标签、列表、表单

Web前端笔记|表格、＜div＞标签、＜span＞标签、列表、表单

目录 表格 简单表格 表格的样式 表格的合并 使用标签 < div>标签 < span>标签 无序列表 有序列表 定义列表 表单 文本框和密码框 单选按钮和复选框 按钮 普通按钮 提交按钮 重置按钮 图像域和文件域 文本域和列表 表格 简单表格 由表题、表头…
阅读更多...
带你开发一个远程控制项目----＞STM32+标准库+阿里云平台+传感器模块+远程显示-------之 MQTT连接阿里云平台

带你开发一个远程控制项目----＞STM32+标准库+阿里云平台+传感器模块+远程显示-------之 MQTT连接阿里云平台

第一篇&#xff1a; (13条消息) 带你开发一个远程控制项目----&#xff1e;STM32标准库阿里云平台传感器模块远程显示。_海口飞鹏岛科技有限公司的博客-CSDN博客 第二篇&#xff1a; (13条消息) 带你开发一个远程控制项目----&#xff1e;STM32标准库阿里云平台传感器模块远程…
阅读更多...
GaussDB pg_rewind和GaussDB rebuild

GaussDB pg_rewind和GaussDB rebuild

GaussDB是一种基于PostgreSQL的关系型数据库&#xff0c;而pg_rewind和Gauss rebuild是GaussDB数据库中用于数据修复和重建的工具&#xff0c;它们具有不同的功能和应用场景。 Gauss rebuild&#xff1a; Gauss rebuild是GaussDB数据库提供的工具&#xff0c;用于进行数据修复和…
阅读更多...
vue 阻止事件冒泡常用的方法

vue 阻止事件冒泡常用的方法

在 Vue 中&#xff0c;阻止事件冒泡有两种常用方法&#xff1a; 1. 使用 event.stopPropagation() 方法&#xff1a; 在事件处理函数中&#xff0c;可以通过调用事件对象的 stopPropagation() 方法来阻止事件冒泡。例如&#xff1a; html <template> <div click"…
阅读更多...
最新文章

Copyright @ 2022~2023