https://leetcode.com/problems/longest-palindromic-subsequence/description/
解题思路:
- 判断sequence两端是否相等,如相等 dp[i][j] = dp[i+1][j-1] + 2;如不相等:dp[i][j] =
Math.max(dp[i - 1][j], dp[i][j - 1]);
代码如下:
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i = len - 1; i >= 0; i--){
dp[i][i] = 1;
for(int j = i + 1; j < len; 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][len - 1];
}
}
网友评论