LC 516 最长回文子序列
题目:
给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。
子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。
输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。
分析:
首先我们可以很清楚地知道,一个回文字符串去掉头和尾之后依然是一个回文字符串。那么一个回文字符s1,假设头尾下标为i,j,那么s1的长度就会等于s1[i-1…j+1]+2。由此可以想到用动态规划解决。
思路:
我们设dp[i] [j]表示为由题目所给字符串s,下标从i到j的最长回文子序列长度。
那么,当0 <= i < n时,dp[i] [i] = 1; 因为每个字符本身就是一个回文子序列。
我们还需要考虑两种情况:
- 当s[i] == s[j] 时 并且 0 <= i < j < n 时,这时是存在由s[i] 和 s[j] 为头尾的回文子序列,因此dp[i] [j] = dp[i+1] [j-1] + 2;
- 当s[i] != s[j] 时 并且 0 <= i < j < n 时,这时由s[i]和s[j]为头尾的字符串一定不是回文子序列, 因此dp[i] [j] = max(dp[i+1] [j],dp[i] [j-1]);
由于我们的状态转移方程是由i+1或者j-1转移过来的,因此当我们在求dp[i] [j] 时一定要保证 dp[i+1] [j] 和 dp[i] [j-1] 以及被访问过了,又因为i < j所以我们需要让i从大到小遍历,让j从i+1到n-1遍历。
代码:
class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n][n]; int res = 0;for(int i = 0;i < n;i++) dp[i][i] = 1;for(int i = n-1;i >= 0;i--){for(int j = i+1;j < n;j++){if(s.charAt(i) == s.charAt(j)){dp[i][j] = dp[i+1][j-1]+2;}else{dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][n-1];}
}