每个自下而上的DP都有相应的自上而下的实现，这是真的吗

Question

我正试图解决这个最长回文子串问题，它返回给定字符串s中最长的回文子字符串。我应该在O(n^2)时间内用DP解决这个问题。这是我的代码：

class Solution:
def longestPalindrome(self, s: str) -> str:
# DP
h = {} #memoization

def dp(i, j): # DP algorithm to compute if the substring s[i:j+1] is palindrome
nonlocal s, h
if (i,j) in h: return h[(i, j)]
else:
if j - i <= 1:
f = s[i] == s[j]
else:
f = dp(i+1, j-1) and s[i] == s[j]
h[(i, j)] = f
return f
res,start, end = 0, 0, 0

for i in range(len(s)):
for j in range(i,len(s)): # All possible substring
if (i,j) in h: temp = h[(i,j)]
else: temp = dp(i, j)
if temp == True and j - i + 1 > res:
res = j-i+1
start = i
end = j
return s[start:end+1]

这个解决方案超过了时间限制，我不确定在我的算法中哪里可以优化。然后我检查了解决方案，发现了一种自下而上的DP算法：

public String longestPalindrome(String s) {
int n = s.length();
String res = null;

boolean[][] dp = new boolean[n][n];

for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);

if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
res = s.substring(i, j + 1);
}
}
}

return res;
}

我如何修改我的自上而下的算法来与上面的自下而上的算法竞争？每个自下而上的DP都有相应的自上而下的方法，具有相同的时间复杂性，这是真的吗？

Answer 1

这种方法是自上而下的DP方法，但效率不是很高与我之前发布的自下而上或直接的相比。

def longestPalindrome(self, s: str) -> str:
if not s: return s
res = ''
n = len(s)
dp = [[False for _ in range(n)] for _ in range(n)]
mx  = 0
for j in range(n):
for i in range(0, j+1):
dp[i][j] = ((s[i] == s[j]) and ((j - i <= 2) or dp[i+1][j-1]))
if dp[i][j]:
if (j-i+1) > mx:
mx  = j-i+1
res = s[i:j+1]
return res