二刷主要记录理解不一样的题
一刷地址：day57
今日题目：困难
今天的题目是从两边往自己搜索dp，其实是区间dp的题
回文子串
dp
class Solution {public int countSubstrings(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];int ans = 0;for(int i = n-1; i >= 0; i--){for(int j = i; j < n; j++){// j - i = 1：表示一个字母的时候，肯定是回文数// j - i = 2：表示两个字母的时候，也是回文数if(s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i+1][j-1])){dp[i][j] = true;ans++;}}}return ans;}
}
双指针 考虑i向两边扩散，或者i+1向两边扩散
class Solution {public int countSubstrings(String s) {int n = s.length();int ans = 0;// i < 2*n-1的目的是让l落在0-n-1之间，相当于以每一个字母左右起始，然后往两边扩散for(int i = 0; i < 2 * n - 1; i++){int l = i / 2;int r = i / 2 + i % 2;while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){l--;r++;ans++;}}return ans;}
}
最长回文子序列
递归
class Solution {String s;int[][] memo;public int longestPalindromeSubseq(String s) {this.s = s;int n = s.length();if(n == 1) return 1;memo = new int[n][n];for(int[] mem: memo) Arrays.fill(mem, -1);return dfs(0, n-1);}int dfs(int i, int j){// 空串if(i > j) return 0;// 只有一个字母if(i == j) return 1;if(memo[i][j] != -1) return memo[i][j];if(s.charAt(i) == s.charAt(j)){// 两个字母，都选memo[i][j] = dfs(i+1, j-1) + 2;}else{// 枚举选哪个memo[i][j] = Math.max(dfs(i+1, j), dfs(i, j-1));}return memo[i][j];}
}
dp
class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] dp = new int[n][n];for(int i = n-1; i >= 0; i--){// 只有一个字母的情况dp[i][i] = 1;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];}
}
