最长回文递归方法当开始和结束的两个字符相等时为什么我们将计数与字符串的其余部分进行比较？

Question

我正在尝试通过递归方法和动态规划来理解 python 中最长回文的解决方案（A- 尚未理解为什么我们称其为动态规划）

我了解基本情况

我明白当两个字符相等时我们移动到字符串中的下一个字符即

c=_longestPalen(st, b+1, e-1, c+2)

B-但是我们为什么要这样做

return bigger(c, bigger(_longestPalen(st, b+1,e,c), _longestPalen(st, b, e-1, c)))

这是完整的代码

def longestPalen(st):
    res=_longestPalen(st, 0,len(st)-1, 0)
    return res

def bigger(x, y):
    if x>y:
        return x
    else:
        return y

def _longestPalen(st, b,e,c):
    if e<b: return c
    if b==e: return c+1
    if st[b] == st[e]:
        c=_longestPalen(st, b+1, e-1, c+2)
        return bigger(c, bigger(_longestPalen(st, b+1,e,c), _longestPalen(st, b, e-1, c)))
    return bigger(_longestPalen(st, b+1, e, 0), _longestPalen(st, b, e-1, 0))

Answer 1

我稍微重组了代码，使其更符合 Python 约定：

def longest_palen(s):
    return _longest_palen(s, 0, len(s) - 1, 0)


def _longest_palen(s, b, e, c):
    if e < b:
        return c
    if b == e:
        return c + 1
    if s[b] == s[e]:
        return max(_longest_palen(s, b + 1, e - 1, c + 2),
                   _longest_palen(s, b + 1, e, c),
                   _longest_palen(s, b, e - 1, c))
    return max(
        _longest_palen(s, b + 1, e, 0),
        _longest_palen(s, b, e - 1, 0)
    )


if __name__ == '__main__':
    print(longest_palen("cyabbaxc"))  # abba   ("cyabbaxc"[2:6])
    print(longest_palen("cabbacxc"))  # cabbac ("cabbacxc"[:6])
    print(longest_palen("cxcabbac"))  # cabbac ("cxcabbac"[2:])

如果当前第一个和最后一个字符相同有四种选择：

当前第一个和最后一个字符都在最长回文中。
- 输入：“阿爸”
- 最长的回文：“阿爸”（4）
只有当前第一个字符在最长回文中。
- 输入：“cabbacxc”
- 最长回文：“cabbac”(6)
- 即使第一个和最后一个字符是“c”，只有第一个字符在最长的回文中，未来的递归步骤需要包括测试“cabbacx”和“cabbac”以获得正确答案。
只有当前最后一个字符在最长回文中。
- 输入：“cxcabbac”
- 最长回文：“cabbac”(6)
- 即使第一个和最后一个字符是“c”，只有最后一个字符在最长的回文中，未来的递归步骤需要包括测试“xcabbac”和“cabbac”以获得正确答案。
当前第一个和最后一个字符都不在最长回文中。
- 输入：“cyabbaxc”
- 最长的回文：“阿爸”（4）
- 这种情况在未来的递归步骤中得到处理，因为下一步将是“yabbax”，我们将在其中处理测试“yabba”和“abbax”。

你之所以如此运行

c = _longestPalen(str, b + 1, e - 1, c + 2)
return bigger(c, bigger(_longestPalen(str, b + 1, e, c), _longestPalen(str, b, e - 1, c)))

或

return max(_longest_palen(s, b + 1, e - 1, c + 2),
           _longest_palen(s, b + 1, e, c),
           _longest_palen(s, b, e - 1, c))

在修改后的实现中，就是要考虑所有这些情况。

这一行的伪代码是这样的：

bigger(both_first_last_included, bigger(only_first_included, only_last_included))

在修改后的实现中，我使用 max，我发现它更清楚地理解正在发生的操作。

max(both_first_last_included, only_first_included, only_last_included)

最长回文递归方法当开始和结束的两个字符相等时为什么我们将计数与字符串的其余部分进行比较？

longest palindrome recursive method when two characters at begin and end are equal why do we compare the count with rest of string?

python

recursion

dynamic-programming