最长回文子序列DP解法能否从字符串起始端开始计算？

我正在解决LeetCode上的最长回文子序列问题，看到一种从字符串末尾开始的DP解法（代码如下）。我想知道是否可以改为从字符串起始端开始循环（示例循环结构如下），但原递推式需要用到未计算的dp[i+1]，请问能否修改递推关系实现从起始端处理，还是只能从末尾开始？

原参考解法代码 #

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1]

期望的循环结构 #

for i in range(0, n):
    for j in range(i+1, n): 
        # ... 

原递推式依赖：

• dp[i][j] = dp[i + 1][j - 1] + 2
• dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

解答 #

可以调整循环顺序从起始端开始，但不能直接套用原递推式，因为原递推依赖的子问题在起始端顺序循环中还未被计算。不过我们可以通过改变遍历逻辑来实现。

核心原因 #

原解法中dp[i][j]表示s[i..j]区间内的最长回文子序列长度，递推时需要用到dp[i+1][j-1]（更短的内部子串）、dp[i+1][j]（i右移一位的子串）。倒序遍历i是因为这些依赖的子串对应的i值更大，会先被计算完成。如果直接从i=0开始顺序遍历，dp[i+1][...]还未赋值，会导致错误。

可行方案：按子串长度从小到大遍历 #

最直观的修改方式是按子串的长度来循环：先处理所有长度为1的子串，再处理长度为2的，直到处理到长度为n的整个字符串。这种方式既符合从起始端处理i的逻辑，又能保证计算dp[i][j]时，所有依赖的子问题都已解决。

代码实现如下：

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        
        # 初始化：长度为1的子串最长回文子序列长度为1
        for i in range(n):
            dp[i][i] = 1
        
        # 遍历子串长度，从2到n
        for length in range(2, n + 1):
            # i是子串起始索引，j是结束索引（j = i + length - 1）
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j]:
                    # 长度为2时，dp[i+1][j-1]为0，直接加2即可
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        
        return dp[0][n-1]

这个方案的时间、空间复杂度和原解法完全一致，都是O(n²)，同时满足你想要的从起始端处理i的逻辑。

关于严格套用你给出的循环结构 #

如果一定要严格使用for i in range(0, n) + for j in range(i+1, n)的嵌套循环，需要重新定义dp[i][j]的含义，但这种方式会让逻辑变得复杂，不如按子串长度遍历的方式直观易懂，实际开发中不推荐。

内容的提问来源于stack exchange，提问作者Maha