LeetCode T647 回文子串
题目链接:647. 回文子串 - 力扣（LeetCode）
题目思路:
我们仍然使用动规五部曲来分析题目
1.确定dp数组含义
这里dp数组表示从下标从i到j这段子串是不是回文子串,是就是true,不是就是false
2.确定dp数组的递推公式
举个例子
这里我们要考虑的就是
s[i] == s[j]
s[i] != s[j]
这两种情况
如果s[i] == s[j]
相等里面还要分
i和j下标相同的情况 --- true
i和j相差一个下标 --- true
i和j相差多个下标的情况 ---判断dp[i + 1][j - 1]是否为true.
判断true的时候让临时变量res++,最后返回res的结果表示数量.
而如果是不等于的情况其实就不同处理,因为默认初始化为false
3.初始化dp数组
直接初始化为false即可,因为如果初始化为true就全部匹配上了
那么我们就就无需初始化即可
4.确定遍历顺序
由于我们要推出dp[i][j] 是由左下角的元素推出的,所以我们得倒序遍历i,再正序遍历j
注意,我们定义的区间是[i,j],这里的j的取值一定是大于等于i的,不然我们的遍历其实就是没有意义的.
5.打印dp数组排错
题目代码:
class Solution {
public int countSubstrings(String s) {
int len = s.length();
int res = 0;
boolean[][] dp = new boolean[len][len];
for(int i = len-1;i>=0;i--){
char c1 = s.charAt(i);
for(int j = i;j<len;j++){
char c2 = s.charAt(j);
if(c1 == c2){
if(j-i<=1){
dp[i][j] = true;
res++;
}else if(dp[i+1][j-1]){
dp[i][j] = true;
res++;
}
}
}
}
return res;
}
}LeetCode T516 最长回文子序列
题目链接:516. 最长回文子序列 - 力扣（LeetCode）
题目思路:
我们也使用动规五部曲来分析题目
1.确定dp数组含义
这里的dp[i][j]表示的[i到j]的闭区间的回文子串的长度
2.确定dp数组的递推公式
这时候也要判断相等和不等的情况
如果s[i] == s[j]
那么就让dp[i+1][j-1]+2
不等的情况我们就在dp[i][j-1]和dp[i-1][j]中选择一个最大值即可
3.初始化dp数组
这里由于我们的递推公式没有计算i == j的情况
可以理解为递推公式是从这个相等的情况出发,向两边扩散,每次需要有两个字母
所以我们要对 dp[i][i] 进行初始化,也就是单个字母的情况,初始化为1即可
4.确定遍历顺序
这个题也是需要反向遍历的,具体让我们看一下递推公式
dp[i][j]是依赖于这三个方向推出的,所以自然有这样的遍历顺序
注:j要从i+1开始到最后,
所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。
5.打印dp数组排错
题目代码:
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i = 0;i<len;i++){
dp[i][i] = 1;
}
for(int i = len-1;i>=0;i--){
char c1 = s.charAt(i);
for(int j = i+1;j<len;j++){
char c2 = s.charAt(j);
if(c1 == c2){
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][len-1];
}
}
