代码随想录 Day48 动态规划16 T647 回文子串 T516最长回文子序列

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数组排错

示例为"aaa"

题目代码:

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];
    }
}