647. 回文子串

题目链接：力扣题目链接

思路：这个需要想到如果两个对比位置小于等于一时候只要相等就成立，但是要是大于一时候就需要判断两者之间是否成立，比如i-j大于1，那么i+1到j-1就应该要成立那么i到j才能成立。因为要判断dp[i + 1][j - 1]是否成立，这个是从左下计算的，所以可以知道这个dp中i要从左下开始遍历。

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

还有一个双指针思路

class Solution {public int countSubstrings(String s) {int len, ans = 0;if (s == null || (len = s.length()) < 1) return 0;//总共有2 * len - 1个中心点for (int i = 0; i < 2 * len - 1; i++) {//通过遍历每个回文中心，向两边扩散，并判断是否回文字串//有两种情况，left == right，right = left + 1，这两种回文中心是不一样的int left = i / 2, right = left + i % 2;while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {//如果当前是一个回文串，则记录数量ans++;left--;right++;}}return ans;}
}

516.最长回文子序列

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];int res = 0;for(int j=0;j<s.length();j++){dp[j][j] = 1;}for(int i=s.length()-1;i>=0;i--){for(int j=i;j<=s.length()-1;j++){if(s.charAt(i)==s.charAt(j)){if(j-i>=1){dp[i][j] = dp[i + 1][j - 1] +2;  }                   }else{dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]);}}}return dp[0][s.length()-1];}
}