【每日一题】最长回文子序列

动态规划：范围尝试模型

范围尝试模型一般根据开头和结尾讨论可能性

f( i , j) 在 str [i:j+1] 上最长回文子序列的长度，终止要求的是 f (0 , len(str)-1)

可能性分析：

f ( i , j ) = { f ( i − 1 , j − 1 ) + 2 ; s t r [ i ] = = s t r [ j ] m a x ( f ( i − 1 , j ) , f ( i , j − 1 ) ) ; s t r [ i ] ! = s t r [ j ] f(i,j)=

f(i,j)={f(i−1,j−1)+2max(f(i−1,j),f(i,j−1))​;str[i]==str[j];str[i]!=str[j]​

• 如果 str[i]==str[j] ，则是在原有 f(i-1,j-1) 子问题的基础上加 2
• 如果 str[i] != str[j] ，则回退到最近的子问题，求最大值

basecase

• 当 i == j 时，如果 str[i] == str[j] 返回 1，否则返回 0。
• 当 i == j + 1 时，如果 str[i] == str[j] 返回 2，否则返回 0。

方案一：暴力递归

def max_sub_palindrome(string):
    if not string: return 0
    t = f(string, 0, len(string) - 1)
    return t


def f(string, i, j):
    if i == j:
        return 1
    if i == j + 1 or i + 1 == j:
        return 2 if string[i] == string[j] else 1

    if string[i] == string[j]:
        return f(string, i + 1, j - 1) + 2
    return max(f(string, i + 1, j), f(string, i, j - 1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方案二：动态规划

def max_sub_palindrome2(string):
    if not string: return 0
    n = len(string)
    dp = [[0] * n for _ in range(n)]

    # base case
    for i in range(n):
        dp[i][i] = 1

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if string[i] == string[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][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方案三：滚动数组

如图（i，j）依赖的左下方的数据，总是被覆盖，在覆盖前需要copy 到一个变量中 tmp：tmp = d[j]

tmp 初始化值根据上述矩阵可知 tmp = 0

def max_sub_palindrome3(string):
    if not string: return 0
    n = len(string)
    dp = [1] * n

    for i in range(n - 2, -1, -1):
        tmp = 0
        for j in range(i + 1, n):
            if string[i] == string[j]:
                new_value = tmp + 2
                down = dp[j]
                dp[j] = new_value
            else:
                new_value = max(dp[j], dp[j - 1])
                tmp = dp[j]
                dp[j] = new_value

    return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

上述三个方案只是求出最长回文子序列的长度。

方案四：动态规划：求最长的回文子序列

在计算完毕最长回文子序列的长度后，能够得到长度和 dp 表。我们可以根据 dp 表反推出最长回文子序列

• 如果 str[i] == str[j] ，i 和 j 跳到 左下边：i ++，j –
• 如果 str[i] != str[j] ，dp[i][j] 与左边或者下边的哪个值相等就跳到对应位置

上述规则可以求出其中一种答案，如果要求出所有答案，可以对 dp 进行深度遍历（dp[i][j] 与 左边和下边都相等，那么这两种情况都需要保留 ）。

def max_sub_palindrome4(string):
    if not string: return ""
    n = len(string)
    dp = [[0] * n for _ in range(n)]

    # base case
    for i in range(n):
        dp[i][i] = 1

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if string[i] == string[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    count = row = 0
    col = n - 1
    res_len = index = dp[row][col]
    res = [None] * index
    while count < res_len:
        if row < n - 1 and dp[row][col] == dp[row + 1][col]:
            row += 1
        elif col > 0 and dp[row][col] == dp[row][col - 1]:
            col -= 1
        else:
            index -= 1
            res[res_len - index - 1] = res[index] = string[row]
            count += 2
            row += 1
            col -= 1
    return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32