动态规划判断回文串的方法 java实现

动态规划是解决回文串问题的一种有效方法，尤其是在需要找出所有可能的回文子串时。动态规划通常涉及创建一个表格，用来保存子问题的解，避免重复计算。下面是一个使用动态规划来判断一个字符串是否是回文串的Java实现示例：

public class PalindromeDynamicProgramming {

    public static boolean isPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = true; // 单个字符总是回文
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i == 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true; // 如果相邻字符相等且子串长度为2或子串是回文，则该子串是回文
                    }
                }
            }
        }

        return dp[0][n - 1]; // 检查整个字符串是否为回文
    }

    public static void main(String[] args) {
        String s = "racecar";
        System.out.println("Is \"" + s + "\" a palindrome? " + isPalindrome(s));
    }
}

在这段代码中，`dp[i][j]`表示字符串从索引`i`到`j`的子串是否为回文。动态规划表被初始化为`false`，然后我们按照字符串的长度填充表格。如果字符`s.charAt(i)`等于`s.charAt(j)`，且子串`s.substring(i, j+1)`的长度小于等于2或者子串`s.substring(i+1, j)`是回文（`dp[i+1][j-1]`为`true`），则`dp[i][j]`被设置为`true`。最后，返回`dp[0][n - 1]`的结果，它表示整个字符串是否为回文。