最长回文子串自顶向下动态规划

Question

s这是使用自下而上动态规划查找给定字符串的最长回文子串的算法。因此，该算法会探索所有可能长度的子串，并检查它是否是1 到 n 中的j有效回文。j由此产生的时间和空间复杂度为O(n^2)。

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s
    P = [[False for _ in range(n)] for _ in range(n)]
    longest = s[0]

    # j is the length of palindrome
    for j in range(1, n+1):
        for i in range(n-j+1):
            # if length is less than 3, checking s[i] == s[i+j-1] is sufficient
            P[i][i+j-1] = s[i] == s[i+j-1] and (j < 3 or P[i+1][i+j-2])
            if P[i][i+j-1] and j > len(longest):
                longest = s[i:i+j]
    return longest 

我正在尝试通过自上而下的记忆方法来实现相同的算法。

问题： 是否可以将该算法转换为自上而下的方法？

关于最长回文子串有很多问题，但他们大多使用这种自下而上的方法。/sf/answers/2097137311/中的答案似乎最接近我的想法。但答案似乎是使用与此不同的算法（并且速度慢得多）。

Answer 1

这是我的递归解决方案：从 i = 0 开始，j = 最大长度如果（i，j）是回文：则最大子串长度为 j-1。否则用 (i+1,j) 和 (i, j-1) 进行递归，并取两者之间的最大值。代码会解释更多。代码是用Java编写的，但我希望它能给出如何实现它的想法。@zcadqe 想要关于如何以自上而下的方法实施的想法。我给出了这个想法，作为奖励，我还给出了 java 代码，以便更好地理解。懂Python的人都可以轻松转换代码！

public class LongestPalindromeSubstringWithSubStr {
static String str;
static int maxLen;
static int startLen;
static int endLen;
static int dp[][];// 0: not calculaed. 1: from index i to j is palindrome

static boolean isPal(int i, int j) {
    if (dp[i][j] != 0) {
        System.out.println("Res found for i:" + i + " j: " + j);
        return (dp[i][j] == 1);
    }
    if (i == j) {
        dp[i][j] = 1;
        return true;
    }
    if (i + 1 == j) {// len 2
        if (str.charAt(i) == str.charAt(j)) {
            dp[i][j] = 1;
            return true;
        }
        dp[i][j] = -1;
        return false;
    }
    if (str.charAt(i) == str.charAt(j)) {
        boolean res = isPal(i + 1, j - 1);
        dp[i][j] = (res) ? 1 : 0;
        return res;
    }
    dp[i][j] = 0;
    return false;
}

// update if whole string from i to j is palindrome
static void longestPalCalc(int i, int j) {
    if (isPal(i, j)) {
        if (j - i + 1 > maxLen) {// update res
            maxLen = j - i + 1;
            startLen = i;
            endLen = j;
        }
    } else {
        longestPalCalc(i + 1, j);
        longestPalCalc(i, j - 1);
    }
}

public static void main(String[] args) {
    str = "abadbbda";
    dp = new int[str.length()][str.length()];
    longestPalCalc(0, str.length() - 1);
    System.out.println("Longest: " + maxLen);
    System.out.println(str.subSequence(startLen, endLen + 1));
}

}