資料結構
網路
關係型資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
安卓系統
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究最長的迴文子序列
最長的迴文子序列是某個給定序列的子序列，並且該子序列是迴文。
在此問題中，給定一個字元序列，我們必須找到最長的迴文子序列的長度。
若要解決此問題，我們可以使用遞迴公式，
如果 L (0, n-1) 用於儲存最長迴文子序列的長度，則
L (0, n-1) := L (1, n-2) + 2（當第 0 個和第 (n-1) 個字元相同時）。
輸入和輸出
Input: A string with different letters or symbols. Say the input is “ABCDEEAB” Output: The longest length of the largest palindromic subsequence. Here it is 4. ABCDEEAB. So the palindrome is AEEA.
演算法
palSubSeqLen(str)
輸入 - 給定的字串。
輸出 - 最長的迴文子序列的長度。
Begin n = length of the string create a table called lenTable of size n x n and fill with 1s for col := 2 to n, do for i := 0 to n – col, do j := i + col – 1 if str[i] = str[j] and col = 2, then lenTable[i, j] := 2 else if str[i] = str[j], then lenTable[i, j] := lenTable[i+1, j-1] + 2 else lenTable[i, j] := maximum of lenTable[i, j-1] and lenTable[i+1, j] done done return lenTable[0, n-1] End
示例
#include<iostream>
using namespace std;
int max (int x, int y) {
return (x > y)? x : y;
}
int palSubseqLen(string str) {
int n = str.size();
int lenTable[n][n]; // Create a table to store results of subproblems
for (int i = 0; i < n; i++)
lenTable[i][i] = 1; //when string length is 1, it is palindrome
for (int col=2; col<=n; col++) {
for (int i=0; i<n-col+1; i++) {
int j = i+col-1;
if (str[i] == str[j] && col == 2)
lenTable[i][j] = 2;
else if (str[i] == str[j])
lenTable[i][j] = lenTable[i+1][j-1] + 2;
else
lenTable[i][j] = max(lenTable[i][j-1], lenTable[i+1][j]);
}
}
return lenTable[0][n-1];
}
int main() {
string sequence = "ABCDEEAB";
int n = sequence.size();
cout << "The length of the longest palindrome subsequence is: " << palSubseqLen(sequence);
}輸出
The length of the longest palindrome subsequence is: 4
更新於： 2020 年 6 月 17 日
863 次瀏覽
廣告