🔴 一字之差：子串 vs 子序列

一个字符串 abcbdcba（8 个字符）。回文就是正着读和倒着读一样。同一个字符串，左边输出最长回文子串的长度，右边输出最长回文子序列的长度：

S = "abcbdcba"

def longest_pal_substr(s):
    best = ""
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            w = s[i:j]
            if w == w[::-1] and len(w) > len(best):
                best = w
    return best

def lps(s):
    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]

print(str(len(longest_pal_substr(S))) + "/" + str(lps(S)))