Algorithm | Leetcode - Dynamic Programming

Dynamic Programming 部分总结

这部分主要总结动态规划。

动态规划最重要的两个点是找：

1. dynamic state；
2. state transition equation

语言： Python3

NO.5 Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解题思路

假定动态规划矩阵为 DP(i,j)，输入字符串为s

• State：DP(l, r) 每个substring s(l:r)是否为一个palindrome，如果是，赋予True值，如果不是，赋予False值
• State transition equation：DP(l,r) = True if s(l) == s(r) and DP(l+1, r-1) = True.
• Base case: DP(l,r) = True if l == r; DP(l,r) = True if s(l) == s(r) and l == r-1;
• 需要注意的一点是 : l <= r 这样在定义 DP矩阵的时候，只关注矩阵的一半右下角就可以了

Solution

def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    N = len(s)
    memo = [[0]*N for _ in range(N)]
    max_len = ''
    for i in range(N):
        i = N - 1 - i
        for j in range(i, N):
            if i == j:
                memo[i][j] = 1
                if 1 > len(max_len):
                    max_len = s[i:j+1]
            elif j - i == 1 and s[i] == s[j]:
                memo[i][j] = 1
                max_len = max(max_len, 2)
                if 2 > len(max_len):
                    max_len = s[i:j+1]
                    
            elif memo[i+1][j-1] == 1 and s[i] == s[j]:
                memo[i][j] = 1
                if j - i + 1 > len(max_len):
                    max_len = s[i:j+1]
                    
    return max_len