package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/26 22:28 */public class LeetCode647 {    public int countSubstrings(String s) {        char[] chars = s.toCharArray();        int len = chars.length;        boolean[][] dp = new boolean[len][len];        int result = 0;        for (int i = len - 1; i >= 0; i--) {            for (int j = i; j < len; j++) {                if (chars[i] == chars[j]) {                    if (j - i <= 1) {                        result++;                        dp[i][j] = true;                    } else if (dp[i + 1][j - 1]) {                        result++;                        dp[i][j] = true;                    }                }            }        }        return result;    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        String s = scanner.next();        int substrings = new LeetCode647().countSubstrings(s);        System.out.println(substrings);    }}

package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/26 22:38 */public class LeetCode516 {    public int longestPalindromeSubseq(String s) {        int len = s.length();        int[][] dp = new int[len + 1][len + 1];        // 从后往前遍历 保证情况不漏        for (int i = len - 1; i >= 0; i--) {            // 初始化            dp[i][i] = 1;            for (int j = i + 1; j < len; 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], Math.max(dp[i][j], dp[i][j - 1]));                }            }        }        return dp[0][len - 1];    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        String s = scanner.next();        int longestPalindromeSubseq = new LeetCode516().longestPalindromeSubseq(s);        System.out.println(longestPalindromeSubseq);    }}