參考鏈接：https://www.cnblogs.com/AndyJee/p/4465696.html

一、題目：最長回文子序列長度

給定字符串，求它的最長回文子序列長度。回文子序列反轉字符順序后仍然與原序列相同。例如字符串abcdfcba中，最長回文子序列長度為7，abcdcba或abcfcba。

思路：動態規劃：時間O（N^2），空間O（N^2）

對于任意字符串，如果頭尾字符相同，那么字符串的最長子序列等于去掉首尾的字符串的最長子序列加上首尾；如果首尾字符不同，則最長子序列等于去掉頭的字符串的最長子序列和去掉尾的字符串的最長子序列的較大者。

例子：abba最長回文子序列個數為4，先判斷首尾的'a'和‘a'是否相等，如果相等則’bb'最長個數+2=4，如果不等，則看'abb'和‘bba'誰的最長個數最大，值為哪個。

因此動態規劃的狀態轉移方程為：

設字符串為str，長度為n，dp[i][j]表示第i到第j個字符間的子序列的個數（i<=j），則：

狀態初始條件：dp[i][i]=1 （i=0：n-1）

狀態轉移方程：dp[i][j]=dp[i+1][j-1] + 2? if（str[i]==str[j]）

? ? ? ? ? ? ? ? ? ?dp[i][j]=max(dp[i+1][j],dp[i][j-1])? if （str[i]!=str[j]）

個數代碼：如果只計算上三角的值，循環從右下方開始

def longestPal(string):if not string :return 0dp = [[0] * len(string) for i in range(len(string))]
　　for i in range(len(s)):
　　　　dp[i][i] = 1
for i in range(len(string)-2,-1,-1):for j in range(i+1,len(string)):if string[i] == string[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j],dp[i][j-1])return dp[0][-1] string= 'abcdfcba' longestPal(string)

二、題目：回文子序列個數

給定字符串，求它的回文子序列個數。回文子序列反轉字符順序后仍然與原序列相同。例如字符串aba中，回文子序列為"a", "a", "aa", "b", "aba"，共5個。內容相同位置不同的子序列算不同的子序列。

思路：動態規劃：時間O（N*N），空間O（N*N）

對于任意字符串，如果頭尾字符不相等，則字符串的回文子序列個數就等于去掉頭的字符串的回文子序列個數+去掉尾的字符串的回文子序列個數-去掉頭尾的字符串的回文子序列個數；如果頭尾字符相等，那么除了上述的子序列個數之外，還要加上首尾相等時新增的子序列個數，1+去掉頭尾的字符串的回文子序列個數，1指的是加上頭尾組成的回文子序列，如aa，bb等。

因此動態規劃的狀態轉移方程為：

設字符串為str，長度為n，p[i][j]表示第i到第j個字符間的最長子序列的長度（i<=j），則：

狀態初始條件：dp[i][i]=1 （i=0：n-1）

狀態轉移方程：dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]? if（str[i]！=str[j]）

? ? ? ? ? ? ? ? ? ?dp[i][j]=dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]+dp[i+1][j-1]+1=dp[i+1][j] + dp[i][j-1]+1? if （str[i]==str[j]）

代碼：

def palNum(string):if not string :return 0dp = [[0] * len(string) for i in range(len(string))]for i in range(len(string)):dp[i][i] = 1for i in range(len(string)-2,-1,-1):for j in range(i+1,len(string)):if string[i] != string[j]:dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1]else:dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1return dp[0][-1] string= 'abba' palNum(string)

?

三、題目：最長回文子串

思路1：借助最長公共子串問題，將原來的string翻轉，求兩個字符串的最長公共子串。

思路2：動態規劃：dp[i,j]=1表示str[i...j]是回文子串，必定存在dp[i+1,j-1]=1。【0

狀態方程：

初始狀態：dp = [[1] * len(n) for i in range(n)]

dp[i][i]=1

思路2代碼：

def longestpalSub(string):if not string :return 0maxres,temp = 0,0dp = [[1] * len(string) for i in range(len(string))]for i in range(len(string)):dp[i][i] = 1for i in range(len(string)-2,-1,-1):for j in range(i+1,len(string)):if string[i] != string[j]:dp[i][j] = 0temp = 0else:dp[i][j] = dp[i+1][j-1]if dp[i][j] == 1:temp = j-i+1maxres = max(maxres,temp)return maxres string= 'cabbaci' longestpalSub(string)

?

?四、題目：回文串個數

思路：動態規劃：dp[i][j]表示子串str[i...j]是否是回文串。

該題創建的dp矩陣和題三是一樣的，但是，題三是求dp[i][j] = 1時，j-i+1最大值，該題求的是dp上三角矩陣出現1的總個數。

初始狀態：dp = [[1] * len(n) for i in range(n)]

dp[i][i]=1

代碼：

#動態規劃if not s:return 0n = len(s)res = ndp = [[1] * n for i in range(n)]
for i in range(n-2,-1,-1):for j in range(i+1,n):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1]if dp[i][j] == 1:res += 1else:dp[i][j] = 0return res

?五、最長的斐波那契子序列的長度

如果序列?X_1, X_2, ..., X_n?滿足下列條件，就說它是?斐波那契式?的：

• n >= 3
• 對于所有?i + 2 <= n，都有?X_i + X_{i+1} = X_{i+2}

給定一個嚴格遞增的正整數數組形成序列，找到 A 中最長的斐波那契式的子序列的長度。如果一個不存在，返回??0 。

（回想一下，子序列是從原序列 A?中派生出來的，它從 A?中刪掉任意數量的元素（也可以不刪），而不改變其余元素的順序。例如，?[3, 5, 8]?是?[3, 4, 5, 6, 7, 8]?的一個子序列）

?

示例 1：

輸入: [1,2,3,4,5,6,7,8] 輸出: 5 解釋: 最長的斐波那契式子序列為：[1,2,3,5,8] 。

示例?2：

輸入: [1,3,7,11,12,14,18] 輸出: 3 解釋: 最長的斐波那契式子序列有： [1,11,12]，[3,11,14] 以及 [7,11,18] 。

?

提示：

• 3 <= A.length <= 1000
• 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
• （對于以 Java，C，C++，以及?C# 的提交，時間限制被減少了 50%）

思路：動態規劃，時間O（n2),空間O（n2)

采用字典dic存儲數組的索引。

dp[i][j]存的是從第i個到第j個最長斐波那契子序列的長度

temp = arr[i] + arr[j]
if temp in dic:
? ? ? ? ? position = dic[temp]
? ? ? ? ? dp[i][j] = dp[j][position] + 1

else:

　　dp[i][j] = 2

代碼：

def lenLongestFibSubseq(A):""":type A: List[int]:rtype: int"""if not A:return 0dic = {}res = 0for i in range(len(A)):dic[A[i]] = idp = [[0] * len(A) for i in range(len(A))]for i in range(len(A)-2,-1,-1):for j in range(i+1,len(A)):temp = A[i] + A[j]if temp in dic:position = dic[temp]dp[i][j] = dp[j][position] + 1res = max(res,dp[i][j])else:dp[i][j] = 2return res

?六、題目：擺動序列

如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為擺動序列。第一個差（如果存在的話）可能是正數或負數。少于兩個元素的序列也是擺動序列。

例如，?[1,7,4,9,2,5] 是一個擺動序列，因為差值 (6,-3,5,-7,3)?是正負交替出現的。相反, [1,4,7,2,5]?和?[1,7,4,5,5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。

給定一個整數序列，返回作為擺動序列的最長子序列的長度。 通過從原始序列中刪除一些（也可以不刪除）元素來獲得子序列，剩下的元素保持其原始順序。

示例 1:

輸入: [1,7,4,9,2,5] 輸出: 6 解釋: 整個序列均為擺動序列。

示例 2:

輸入: [1,17,5,10,13,15,10,5,16,8] 輸出: 7 解釋: 這個序列包含幾個長度為 7 擺動序列，其中一個可為[1,17,10,13,10,16,8]。

示例 3:

輸入: [1,2,3,4,5,6,7,8,9] 輸出: 2

思路：時間O（n2),空間O（n2）

兩個dp數組p和q，

p[i]表示到i位置時首差值為正的擺動子序列的最大長度，

q[i]表示到i位置時首差值為負的擺動子序列的最大長度。

我們從i=1開始遍歷數組，然后對于每個遍歷到的數字，再從開頭位置遍歷到這個數字，然后比較nums[i]和nums[j]，分別更新對應的位置

p[i] = max(p[i],q[j]+1)【nums[i] > nums[j]】

q[i] = max(q[i],p[j] + 1) 【nums[i] < nums[j] 】

代碼：

def wiggleMaxLength(nums):""":type nums: List[int]:rtype: int"""if not nums:return 0p = [1] * len(nums)q = [1] * len(nums)for i in range(1,len(nums)):for j in range(0,i):if nums[i] > nums[j]:p[i] = max(p[i],q[j] + 1)elif nums[i] < nums[j]:q[i] = max(q[i],p[j] + 1)return max(q[-1],p[-1])

?

轉載于:https://www.cnblogs.com/Lee-yl/p/9988704.html

總結

以上是生活随笔為你收集整理的算法62---最长回文子序列长度（子串）、回文子序列总共个数（子串）【动态规划】...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。