問題描述：

回文是正序與逆序相同的非空字符串，例如“civic”、“racecar”都是回文串。任意單個字符的回文是其本身。

求最長回文子序列要求在給定的字符串中找出最長的回文子序列（即找出的序列不要求在原序列中連續(xù)）。

例如，序列A=“javaej”，其最長回文子序列為“javaj”，長度為5。

遞推關(guān)系：

其子問題的填充順序為（以javaej為例）：

?

算法實現(xiàn)：

package agdp; public class LPS {public static int getLPS(String str){int n = str.length();int[][] aux = new int[n][n];for (int i = 0; i < n; i++) {aux[i][i] = 1;//單子字符，最長回文子序列長度為1 }for (int l = 2; l <= n; l++) {//子序列長度，從2到nfor (int i = 0,j; i <= n-l; i++) {j = l+i-1;if (str.charAt(i) == str.charAt(j)) {aux[i][j] = aux[i+1][j-1]+2;//首尾元素相等，必是回文子序列中的元素}else {//首尾元素不等，取(i+1)->j序列和i->(j-1)系列中較長的回文子序列aux[i][j] = Math.max(aux[i+1][j], aux[i][j-1]);}}}return aux[0][n-1];}public static void main(String[] args) {// TODO Auto-generated method stub // String str = "character";;String str = "javaej";int result = getLPS(str);System.out.println(result);} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qcblog/p/7819393.html

總結(jié)

以上是生活随笔為你收集整理的最长回文子序列(LPS)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。