您现在的位置是：首页 >技术交流 >代码随想录算法训练营第五十七天 |动态规划 part17网站首页技术交流

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindromic-substrings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        // dp[i][j]表示 [i,j]的字串是否是回文字符串
        boolean [][] dp = new boolean[len][len];
        // s[i],s[j] 不相同那么返回False
        // s[i],s[j] 相同
        // 下标i和j相同，同一个字符 ->回文字符串
        // 下标i和j相差1，如aa ->回文字符串
        // 下标i和j相差大于1，那么检查[i+1,j-1]是否为回文
        // 遍历顺序从下到上从左到右
        for(int i=len-1;i>=0;i--){
            char charI = s.charAt(i);
            for(int j=i;j<len;j++){
                char charJ = s.charAt(j);
                if(charI==charJ){
                    if(i==j ||j-i==1){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }else{
                    dp[i][j]=false;
                }
            }
        }
        int res = 0;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(dp[i][j]==true) res +=1;
            }
        }
        return res;
    }
}

 516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int longestPalindromeSubseq(String s) {
        // 回文子序列 不是连续的
        int len = s.length();
        // dp[i][j]字符串s在范围内最长的回文子序列为dp[i][j]
        int [][] dp = new int[len][len];
        // 初始化
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                // 一个字符的字符串最长回文子序列为1
                if(i==j) dp[i][j] = 1;
            }
        }
        // 如果s[i] == s[j] 那么dp[i][j] = dp[i+1][j-1] + 2
        // 如果s[i] != s[j] 那么dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
        // 遍历顺序从下到上，从左到右
        for(int i=len-1;i>=0;i--){
            char charI = s.charAt(i);
            for(int j=i+1;j<len;j++){
                char charJ = s.charAt(j);
                if(charI==charJ){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    // i,j 不能同时放，尝试放一个，然后取三种情况取最大值
                    dp[i][j] = Math.max(Math.max(dp[i+1][j],dp[i][j]),dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}