本文主要是介绍93、动态规划-最长回文子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路
首先从暴力递归开始，回文首尾指针相向运动肯定想等。就是回文，代码如下：
public String longestPalindrome(String s) {if (s == null || s.length() == 0) {return "";}return longestPalindromeHelper(s, 0, s.length() - 1);}// 递归方法，用于寻找从left到right范围内的最长回文子串private String longestPalindromeHelper(String s, int left, int right) {if (left == right) {return s.substring(left, right + 1); // 如果左右指针相等，说明是单个字符，单个字符本身是回文}// 如果当前字符串是回文，直接返回这个子串if (isPalindrome(s, left, right)) {return s.substring(left, right + 1);}// 不是回文时，尝试两种情况：忽略左边字符或忽略右边字符String leftPalindrome = longestPalindromeHelper(s, left + 1, right); // 忽略左边字符String rightPalindrome = longestPalindromeHelper(s, left, right - 1); // 忽略右边字符// 比较这两种情况，返回更长的那个回文子串return leftPalindrome.length() > rightPalindrome.length() ? leftPalindrome : rightPalindrome;}// 辅助方法，用于检查给定字符串s从left到right的部分是否是回文private boolean isPalindrome(String s, int left, int right) {while (left < right) { // 双指针法检查是否回文if (s.charAt(left) != s.charAt(right)) {return false; // 一旦发现不对称，立即返回false}left++; // 移动左指针right--; // 移动右指针}return true; // 所有字符均对称，是回文}递归面临很多重复计算，这个时候可以使用动态规划
动态规划的思路：
- 状态定义：定义
dp[i][j]为布尔值，表示字符串从索引i到索引j的子串是否为回文。 - 初始化：单个字符总是回文，所以对于所有
i，dp[i][i]是true。 - 状态转移方程：如果
s[i]和s[j]相等，并且内部的子串也是回文（即dp[i+1][j-1]是true或者i和j之间的距离小于等于2），那么dp[i][j]也应该是true。 - 从底向上填表：由于每个状态依赖于左下方的状态（即
dp[i+1][j-1]），我们需要从下向上和从左到右填充这个表。
public String longestPalindrome(String s) {if (s == null || s.length() == 0) {return "";}int n = s.length();boolean[][] dp = new boolean[n][n];String longest = "";// 填充动态规划表for (int len = 1; len <= n; len++) { // len 是当前子串的长度for (int start = 0; start < n; start++) {int end = start + len - 1;if (end >= n) { // 确保不越界break;}// 设置dp[start][end]的值dp[start][end] = (s.charAt(start) == s.charAt(end)) && (len <= 2 || dp[start + 1][end - 1]);// 如果当前子串是回文，检查它是否是最长的回文if (dp[start][end] && len > longest.length()) {longest = s.substring(start, end + 1);}}}return longest;}这篇关于93、动态规划-最长回文子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
