代码随想录算法训练营第四十四天-647回文子串、516最长回文子序列

前言
状态：647 看解析，516 看解析
更新

1 2	24-07-09 初始记录 24-07-10 完成

初步题解

647 回文子串

题目链接：(https://leetcode.cn/problems/palindromic-substrings)

516 最长回文子序列

题目链接：(https://leetcode.cn/problems/longest-palindromic-subsequence)

确定 dp[i][j] 的含义：表示区间范围 [i,j] （注意是左闭右闭）的子串的最长回文子串的长度。
递推公式：s[i] 与 s[j] 相等，s[i] 与 s[j] 不相等这两种情况：不相等取左右指针向内移动的最大值；相等 dp[i][j] = dp[i + 1][j - 1] + 2;
dp 数组的初始化：相等时，取 1。
遍历顺序：从下到上，从左到右遍历
打印 dp 数组（用于 debug）

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;  
    }  
  
    int max= 0;  
    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]);  
            }  
            max = Math.max(dp[i][j], max);  
        }  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return max;  
}

看解析

647 回文子串

解析：(https://programmercarl.com/0647.回文子串.html)

确定 dp[i][j] 的含义：表示区间范围 [i,j] （注意是左闭右闭）的子串是否是回文子串，如果是 dp[i][j] 为 true，否则为 false。
递推公式：s[i] 与 s[j] 相等，s[i] 与 s[j] 不相等这两种情况：不相等即为 false；相等分为三种情况：下标 i 与 j 相同，同一个字符返回 true；下标 i 与 j 相差为 1，返回 true；i 与 j 相差大于 1 的时候，判断 dp[i + 1][j - 1] 是否为 true
dp 数组的初始化：全为 false
遍历顺序：从下到上，从左到右遍历
打印 dp 数组（用于 debug）

public int countSubstrings(String s) {  
    boolean[][] dp = new boolean[s.length()][s.length()];  
  
    int num = 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)) {  
                dp[i][j] = false;  
            } else {  
                if (j - i <= 1) {  
                    dp[i][j] = true;  
                } else {  
                    dp[i][j] = dp[i + 1][j - 1];  
                }  
            }  
            if (dp[i][j]) {  
                num++;  
            }  
        }  
    }  
  
    System.out.println(Arrays.deepToString(dp));  
  
    return num;  
}

516 最长回文子序列

解析：(https://programmercarl.com/0516.最长回文子序列.html)