是不是每一个自下而上的DP都有对应的自上而下的实现？

Question

我正在尝试解决这个 Longest Palindromic Substring 问题，其中 returns 是给定字符串 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;
}

如何修改我的自上而下算法以与上述自下而上算法竞争？是不是每个bottom-up DP都有对应的时间复杂度相同的top-down方法？

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

是不是每一个自下而上的DP都有对应的自上而下的实现？

Is it true that every bottom-up DP has a corresponding top-down realization?

iteration

recursion

dynamic-programming