标签搜索

目 录CONTENT

文章目录

最长回文子序列.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 9 阅读 / 2,464 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

最长回文子序列

@[toc]

一、问题描述

给定一个字符串s,找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:

输入:

"bbbab"
输出:

4
一个可能的最长回文子序列为 "bbbb"。

示例 2:

输入:

"cbbd"
输出:

2
一个可能的最长回文子序列为 "bb"。

二:动态规划之⼦序列问题解题模板

⼦序列问题是常⻅的算法问题, ⽽且并不好解决。

⾸先, ⼦序列问题本⾝就相对⼦串、 ⼦数组更困难⼀些, 因为前者是不连续的序列, ⽽后两者是连续的, 就算穷举你都不⼀定会, 更别说求解相关的算法问题了

两种思路

1、 第⼀种思路模板是⼀个⼀维的 dp 数组:

int n = array.length;
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
	for (int j = 0; j < i; j++) {
		dp[i] = 最值(dp[i], dp[j] + ...)
	}
}

举个我们写过的例⼦「最⻓递增⼦序列」 , 在这个思路中 dp 数组的定义是:

在⼦数组 array[0..i] 中, 我们要求的⼦序列(最⻓递增⼦序列) 的⻓度是 dp[i] 。

2、 第⼆种思路模板是⼀个⼆维的 dp 数组:

int n = arr.length;
int[][] dp = new dp[n][n];
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		if (arr[i] == arr[j])
			dp[i][j] = dp[i][j] + ...
		else
			dp[i][j] = 最值(...)
	}
}

本思路中 dp 数组含义⼜分为「只涉及⼀个字符串」 和「涉及两个字符串」 两种情况。

2.1 涉及两个字符串/数组时(⽐如最⻓公共⼦序列) , dp 数组的含义如下:

在⼦数组 arr1[0..i] 和⼦数组 arr2[0..j] 中, 我们要求的⼦序列(最⻓公共⼦序列) ⻓度为 dp[i][j] 。

2.2 只涉及⼀个字符串/数组时(⽐如最⻓回⽂⼦序列) , dp 数组的含义如下

在⼦数组 array[i..j] 中, 我们要求的⼦序列(最⻓回⽂⼦序列) 的⻓度为 dp[i][j] 。

三:最长回文子序列解法思路

对于这个问题对 ==dp 数组的定义是: 在⼦串 s[i..j] 中, 最⻓回⽂⼦序列的⻓度为 dp[i][j]== 。 ⼀定要记住这个定义才能理解算法。

在这里插入图片描述
为啥这个问题要这样定义⼆维的 dp 数组呢? 我们多次提到, 找状态转移需要归纳思维, 说⽩了就是如何从已知的结果推出未知的部分, 这样定义容易归纳, 容易发现状态转移关系

具体来说, 如果我们想求 dp[i][j] , 假设你知道了⼦问题 dp[i+1][j-1]的结果( s[i+1..j-1] 中最⻓回⽂⼦序列的⻓度) , 你是否能想办法算出dp[i][j] 的值( s[i..j] 中, 最⻓回⽂⼦序列的⻓度) 呢?
在这里插入图片描述

可以! 这取决于 s[i] 和 s[j] 的字符

如果它俩相等那么它俩加上 s[i+1..j-1] 中的最⻓回⽂⼦序列就是s[i..j] 的最⻓回⽂⼦序列
在这里插入图片描述

如果它俩不相等说明它俩不可能同时出现在 s[i..j] 的最⻓回⽂⼦序列中, 那么把它俩分别加⼊ s[i+1..j-1] 中, 看看哪个⼦串产⽣的回⽂⼦序列更⻓即可

在这里插入图片描述

以上两种情况写成代码就是这样:

if (s[i] == s[j])
	// 它俩⼀定在最⻓回⽂⼦序列中
	dp[i][j] = dp[i + 1][j - 1] + 2;
else
	// s[i+1..j] 和 s[i..j-1] 谁的回⽂⼦序列更⻓?
	dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

明确⼀下 base case, 如果只有⼀个字符, 显然最⻓回⽂⼦序列⻓度是1, 也就是 dp[i][j] = 1 (i == j) 。

因为 i 肯定⼩于等于 j , 所以对于那些 i > j 的位置, 根本不存在什
么⼦序列, 应该初始化为 0

另外, 看看刚才写的状态转移⽅程, 想求 dp[i][j] 需要知道 dp[i+1][j-1] , dp[i+1][j] , dp[i][j-1] 这三个位置; 再看看我们确定的 base case, 填⼊ dp 数组之后是这样:

在这里插入图片描述

为了保证每次计算 dp[i][j] , 左下右⽅向的位置已经被计算出来, 只能斜着遍历或者反着遍历

在这里插入图片描述

方法一:DP table解法

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));

        //根据base case的定义:当只剩下一个字符的时候,直接return 1,因为字符本身和自己肯定是满足回文
        //关系的,有根据dp数组的定义,dp[i][j]代表在[1...j]区间内最长的回文子序列的长度,什么情况下只
        //剩下一个字符呢,当i == j的时候,不就代表只剩下一个字符了,在DP table中,直接把相应位置置为1即可
        for(int i = 0;i < s.size();i++)
        {
            dp[i][i] = 1;
        }

        //只能反向或者斜向遍历,详情请看博客
        for(int i = s.size() - 1;i >= 0;i--)
        {
            for(int j = i + 1;j < s.size();j++)
            {
                if(s[i] == s[j])//如果当前两个字符相等,就把dp[i + 1][j - 1]当最长回文子序列当长度 + 2即可
                {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else//反之,1.i位置处当元素在最长回文子序列当中;2.j位置处当元素在最长回文子序列当中;
                //3.都不在最长回文子序列当中;主要是1,2两种情况,第3种情况的最长回文子序列长度只会比1,2两种情况小,
                //取1,2两种情况中最大的返回即可
                {
                    dp[i][j] = max(dp[i + 1][j],dp[i][j - 1]);
                }
            }
        }

        //根据博客当中的图,最后的结果并不在[max][max]或者[0][0],而是在[0][max]当中
        return dp[0][s.size() - 1];
    }
};

方法二:DP函数(有点难控制,为了我的头发决定你们自己搞)

0

评论区