Dynamic programming: Longest palindrome substring and subsequence

1. Palindrome string

Palindrome string is the same string read forward and backward , for example aba,aabb etc. , Given a string , Find the longest text substring . Note that substring refers to continuous

1.1 Expand left and right

The idea of left-right expansion is very interesting , If a problem uses the idea of left-right expansion , For so long, it is directly set in two ranges l,r, In this way, the parity problem can be avoided

A very direct idea is to start with a character , Start searching on both sides , Then match whether the characters are equal

	<— Search left	A certain character	Search right —>
character string	a	b	a
Search boundaries	l		r

It's easy to think of two situations, odd and even , When odd （‘aba’） when l=r=i, Then move to both sides , When it is even (‘aabb’) when l=i,r=i+1

def helper(s,l,r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l+1:r]
       
def longs(s):
    res = ''
    for i in range(len(s)):
        tmp = helper(s,i,i) #  Odd number 
        if len(tmp) > len(res):res = tmp
        tmp = helper(s,i,i+1) #  even numbers 
        if len(tmp) > len(res):res = tmp
    print(len(res))

s = input()
n = len(s)

longs(s)

1.2 Dynamic programming

The idea of dynamic planning is also very simple , If i+1~j-1 The palindrome string , So if s[i]==s[j] be i~j The string between is also a palindrome substring , If it's not equal , Then it's not a palindrome substring , Thus, the state transition equation can be listed dp[i][j]=dp[i+1][j-1] and s[i]==s[j]. Then we consider the initial conditions , If i==j be dp[i][i]=True, When a character is positive, the palindrome string , Two and three characters are dp[i][j] = (s[i] == s[j]), Just consider the characters on both sides .
You can see , Calculation dp[i][j] Used the future state dp[i+1][j], therefore i Reverse iteration is required , That is, large to small .

Original string	a	b	c	a	c	b	a
Subsequence 1	a	b			b		a

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for j in range(n)] for i in range(n)]
        max_len = 0
        max_str = ''

        for i in range(n-1,-1,-1):
            for j in range(i,n):
                if s[i] == s[j]:
                    if j-i<=2:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    max_str = s[i:j+1]
        return max_str

The longest palindrome subsequence

One of the main differences between subsequence and substring is whether it is connected , Characters do not need hyphenation , for instance

Original string	a	b	c	a	b	c	a
Subsequence 1	a	b			b		a
Subsequence 2	a		c			c	a
Subsequence 3	a			a			a
Subsequence 4	a		c	a		c	a
Subsequence 5	a	b		a	b		a
Subsequence n	…

You can see that palindrome subsequences do not need to be continuous at all , Now the problem is how to solve the longest subsequence ？ If we find i+1~j-1 The longest subsequence between , So how to solve i~j The longest subsequence between ？

i	i+1						j-1	j
s[i]	a	b	c	a	b	c	a	s[j]

We assume that dp[i+1][j-1] Is string i+1~j-1 The length of the longest palindrome subsequence of ,

1. When s[i]==s[j] when , Yes dp[i][j] = dp[i+1][j-1]+2

i	i+1						j-1	j
s[i]	a	b	c	a	b	c	a	s[j]

2. When s[i]!=s[j] when , It's interesting at this time , It can also be divided into two situations , The first kind of time demand i+1~j The longest palindrome sequence between , The second is to ask i~j-1 The longest palindrome subsequence between

	i	i+1						j-1	j
original	s[i]	a	b	c	a	b	c	a	s[j]
i+1~j		a	b	c	a	b	c	a	s[j]
i~j-1	s[i]	a	b	c	a	b	c	a

At this time there is dp[i][j]=max(dp[i][j-1],dp[i+1][j])

We have got the state transition equation , The next step is to see base, You can know dp[i][i]=1, Because we have always been i~j, So there is j>i, If j<i, Then it is impossible to get the palindrome sequence , So there is dp[i][j]=0 if j < i

Now there is only one boundary problem , seek dp[i][j] Need to use dp[i+1][j], That is to solve i The position of the future is used i+1 Location , In order to ensure normal calculation , We need to i Update in a decreasing way ,j It uses j and j-1, So use incremental calculation

    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[1 if i==j else 0 for i in range(n)] for j in range(n)]
        for i in range(n-1,-1,-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][-1]