两个求解目标类似的题目，对比记忆！

5.最长回文子串

题目

法1：二维DP

最基础方法！必须掌握！
O(N^2) + O(N^2)

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n == 1) {return s;}String res = s.substring(0, 1);boolean[][] dp = new boolean[n][n];for (int i = 0; i < n; ++i) {dp[i][i] = true;}for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {dp[i][j] = (j - i == 1 || dp[i + 1][j - 1]) && (s.charAt(i) == s.charAt(j));if (dp[i][j] && (j - i + 1 > res.length())) {res = s.substring(i, j + 1);} }}return res;}
}

法2：中心扩展法

O(N^2) + O(1)

class Solution {public String longestPalindrome(String s) {if (s.length() < 2) {return s;}String res = "";for (int i = 0; i < s.length(); ++i) {String res1 = palindrome(s, i, i);String res2 = palindrome(s, i, i + 1);res = res1.length() > res.length() ? res1 : res;res = res2.length() > res.length() ? res2 : res;}return res;}public String palindrome(String s, int i, int j) {while (i >= 0 && j < s.length() && (s.charAt(i) == s.charAt(j))) {--i;++j;}return s.substring(i + 1, j);}
}

516.最长回文子序列

题目

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n][n];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] = (j - i == 1 ? 0 : 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];}
}