最长回文子序列问题

最长回文子序列问题

问题描述：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

注意是子序列而不是子串！
子串是连续的，比如”abda”最长回文子串就是”a”或者”b”…
子序列是不连续的，比如”abda”最长子序列就是”aba”或者”ada”

示例

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。

一般来说，这类问题都是让你求一个最长子序列，因为最短子序列就是一个字符。一旦涉及到子序列和最值，考察的是动态规划技巧，时间复杂度一般都是 O(n^2)。

既然要用动态规划，那就要定义 dp 数组，找状态转移关系。

1

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] + ...)}
}

2

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] + ...elsedp[i][j] = 最值(...)}
}

该文章会更新，欢迎大家批评指正。

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，
分享给大家：[Linux，Nginx，ZeroMQ，MySQL，Redis，
fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，
TCP/IP，协程，DPDK等技术内容，点击立即学习:
服务器课程：C++服务器