算法训练营第五十九天|LeetCode647、516

题目连接：647. 回文子串 - 力扣（LeetCode）

个人思路：dp数组的含义是：dp[i][j]：s字符串下标i到下标j的字串是否是一个回文串

这里我出现了错误

为什么出错呢？代码如下：

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

我错把j-i写成了i-j，因为j是不断往上加的，所以到了最后两端的时候，j肯定比i大，这个时候i-j就肯定是负数，那么结果就会误加1，这就是我错误的由来

还有一个错误是数组越界

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

    }
}

我错误的把j初始化成0，而且j-i也写成了i-j，i-j为什么会数组越界呢？理由是此时i-j>1那么就会触发这个代码

因为j初始化为0，所以j-1必然-1因此报错

然后j不能初始化成0的原因是会造成重复

代码

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

题目链接：516. 最长回文子序列 - 力扣（LeetCode）

个人思路：这道题也简单，dp数组的含义是字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

初始化是基于递推公式推导的，如果循环到两个最外层字符相等时，那么dp[i][j] = dp[i+1][j-1]+2;

如果不相等，那么就考虑取i到j-1的范围或者i+1到j的范围，从中选择最大值。

此外，两个指针遍历的过程中，会指向相同元素，这是递推公式所没有考虑到的，因此当指向相同元素的时候，也就是指向了一个元素，那么单个元素的最长回文子序列是1，因此使用for循环初始化成1

代码

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for(int i=0;i<s.length();i++){
            dp[i][i] = 1;
        }
        for(int i=s.length()-1;i>=0;i--){
            for(int j = i+1;j<s.length();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]);
                }
            }
        }
        int res = 0;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<s.length();j++){
                res = Math.max(dp[i][j],res);
            }
        }
        return res;
    }
}