最长回文子序列问题
最长回文子序列问题
问题描述:给你一个字符串 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++服务器