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

題目見如下鏈接
【最長回文子串】
思路：
(1)中心擴(kuò)展：遍歷字符串中的字符胜臊，找出能構(gòu)成回文子串的左右邊界灼芭，通過不斷地比較得到最長的子串椒振。
(2)動態(tài)規(guī)劃: dp數(shù)組的定義為從i到j(luò)能否構(gòu)成回文子串效诅，是一個布爾數(shù)組，動態(tài)方程轉(zhuǎn)化的形式為:

 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]

然后保存最長的結(jié)果和開始的值霎匈，用作最后的返回

整個的代碼如下：
class Solution:
    def longestPalindrome(self, s: str) -> str:
    # 中心擴(kuò)展算法
    #    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):
    #奇數(shù)
    #        oddstr=Center(s,i,i)
    #偶數(shù)
    #        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動態(tài)規(guī)劃 dp【i][j]表示的是從i到j(luò)字符能否構(gòu)成回文子串是一個bool數(shù)組
        l=len(s)
        dp=[[False]*l for _ in range(l)]
        #開始dp算法
        start=0
        val=0
        for j in range(l):
            #對角元素設(shè)置為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.字符串中的最長回文子序列

題目見如下鏈接
【最長回文子序列】
思路：
動態(tài)規(guī)劃的核心思想是從已知推算未知戴差，這里對于dp數(shù)組的定義十分重要，本題對于數(shù)組dp的定義如下,dp[i][j]表示從i到j(luò)的最長回文子序列铛嘱，則dp[i][j]的計(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]);

知道了動態(tài)轉(zhuǎn)移方程，需要初始化一些值墨吓，這里需要注意的是需要倒著往前遍歷球匕，原因在于動態(tài)轉(zhuǎn)移方程的形式：

image.png

實(shí)現(xiàn)代碼如下所示：

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]表示從字符i到字符j能構(gòu)成的最長回文子序列的長度
        #這里要注意的是倒著遍歷
        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])

總結(jié)

對于動態(tài)規(guī)劃問題求解dp數(shù)組的問題帖烘，dp數(shù)組的定義非常重要亮曹，同時寫出從已知推未知的動態(tài)規(guī)劃轉(zhuǎn)移方程能達(dá)到事半功倍的效果。

2.LCS最長公共子序列

題目鏈接：
【最長公共子序列】
思路：
其中的max部分有點(diǎn)類似于最長回文子序列，這里對比兩個字符串的時候如果末尾字符相等則在之前一位計(jì)算的動態(tài)規(guī)劃數(shù)組中+1照卦，而最長公共子串則是判斷相等在其基礎(chǔ)上加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]