1.字符串中的最长回文子串

题目见如下链接
【最长回文子串】
思路：
(1)中心扩展：遍历字符串中的字符，找出能构成回文子串的左右边界，通过不断地比较得到最长的子串。
(2)动态规划: dp数组的定义为从i到j能否构成回文子串，是一个布尔数组，动态方程转化的形式为:

 if j-i<2:
       dp[i][j]=s[i]==s[j]
 else:
       dp[i][j]=dp[i+1][j-1] and s[i]==s[j]

然后保存最长的结果和开始的值，用作最后的返回

整个的代码如下：
class Solution:
    def longestPalindrome(self, s: str) -> str:
    # 中心扩展算法
    #    def Center(s,left,right):
    #        while left>=0 and right<len(s) and s[left]==s[right]:
    #            left-=1
    #            right+=1
    #        return s[left+1:right]
    #    l=len(s)
    #    max_len=1
    #    res=''
    #    for i in range(l):
    #奇数
    #        oddstr=Center(s,i,i)
    #偶数
    #        evenstr=Center(s,i,i+1)
    #        temp=oddstr if len(oddstr)>len(evenstr) else evenstr
    #        if len(temp)>len(res):res=temp
    #    return res
        #dp动态规划 dp【i][j]表示的是从i到j字符能否构成回文子串是一个bool数组
        l=len(s)
        dp=[[False]*l for _ in range(l)]
        #开始dp算法
        start=0
        val=0
        for j in range(l):
            #对角元素设置为True
            dp[j][j]=True
            for i in range(j+1):
                if j-i<2:
                    dp[i][j]=s[i]==s[j]
                else:
                    dp[i][j]=dp[i+1][j-1] and s[i]==s[j]
                if dp[i][j]==True and j-i+1>val:
                    val=j-i+1
                    start=i
        print(dp)
        return   s[start:start+val]    

2.字符串中的最长回文子序列

题目见如下链接
【最长回文子序列】
思路：
动态规划的核心思想是从已知推算未知，这里对于dp数组的定义十分重要，本题对于数组dp的定义如下,dp[i][j]表示从i到j的最长回文子序列，则dp[i][j]的计算分为如下两种情况:

if (s[i] == s[j])
    // 它俩一定在最长回文子序列中
    dp[i][j] = dp[i + 1][j - 1] + 2;
else
    // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

知道了动态转移方程，需要初始化一些值，这里需要注意的是需要倒着往前遍历，原因在于动态转移方程的形式：

image.png

实现代码如下所示：

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]表示从字符i到字符j能构成的最长回文子序列的长度
        #这里要注意的是倒着遍历
        l=len(s)
        dp=[[0]*l for _ in range(l)]
        #记录的是长度，对角线的值为1
        for i in range(l):
            dp[i][i]=1
        #这里的range需要注意的是不会包含后面的
        for i in range(l-2,-1,-1):
            for j in range(i+1,l,1):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])
        return max(dp[0])

总结

对于动态规划问题求解dp数组的问题，dp数组的定义非常重要，同时写出从已知推未知的动态规划转移方程能达到事半功倍的效果。

2.LCS最长公共子序列

题目链接：
【最长公共子序列】
思路：
其中的max部分有点类似于最长回文子序列，这里对比两个字符串的时候如果末尾字符相等则在之前一位计算的动态规划数组中+1，而最长公共子串则是判断相等在其基础上加2。

代码如下：

 def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        l1=len(text1)
        l2=len(text2)
        dp=[[0]*(l2+1) for _ in range(l1+1)]
        for i in range(l1):
            for j in range(l2):
                if text1[i]==text2[j]:
                    dp[i+1][j+1]=dp[i][j]+1
                else:
                    dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
        return dp[-1][-1]