本文涉及知識點

動態規劃匯總

LeetCode1771. 由子序列構造的最長回文串的長度

給你兩個字符串 word1 和 word2 ，請你按下述方法構造一個字符串：
從 word1 中選出某個 非空 子序列 subsequence1 。
從 word2 中選出某個 非空 子序列 subsequence2 。
連接兩個子序列 subsequence1 + subsequence2 ，得到字符串。
返回可按上述方法構造的最長 回文串 的 長度 。如果無法構造回文串，返回 0 。
字符串 s 的一個 子序列 是通過從 s 中刪除一些（也可能不刪除）字符而不更改其余字符的順序生成的字符串。
回文串 是正著讀和反著讀結果一致的字符串。
示例 1：
輸入：word1 = “cacb”, word2 = “cbba”
輸出：5
解釋：從 word1 中選出 “ab” ，從 word2 中選出 “cba” ，得到回文串 “abcba” 。
示例 2：
輸入：word1 = “ab”, word2 = “ab”
輸出：3
解釋：從 word1 中選出 “ab” ，從 word2 中選出 “a” ，得到回文串 “aba” 。
示例 3：
輸入：word1 = “aa”, word2 = “bb”
輸出：0
解釋：無法按題面所述方法構造回文串，所以返回 0 。
提示：
1 <= word1.length, word2.length <= 1000
word1 和 word2 由小寫英文字母組成

動態規劃

word3 = word1 + word2
n1 = word1.length
n2 = word2.length
n = word3.length

動態規劃的狀態表示

dp[i][j] 表示 words[i…j-1]的最長回文子序列。
空間復雜度： O(nn)

動態規劃的轉移方程

dp[i][j] = max(dp[i+1][j],dp[i][j-1]
如果words[i] 等于words[j]， dp[i][j] = MaxSelf( dp[i+1][j-1])+2)
單個狀態轉移的時間復雜度：O(1)
故總的時間復雜度為：O(nn)
$$dp[i][j]=?\begin{array}{llc}dp[i][j?1]& & dp[j?1]不在回文串中\\ dp[i+1][j?1]& & s[i]和s[j?1]對應\\ dp[i+1][j]& & s[j?1]和其它字符對應\end{array}$$

動態規劃的初值值

長度為1的子串 dp[i][j]全部為1，長度為0的子串，dp[i][j]全部為0。

動態規劃的填表順序

len 從2到N

動態規劃的返回值

( i < n1 )&& ( j >= n1) 最大值 (2+dp[i+1][j])
回文串的首字符必須在word1，尾字符必須在word2。

代碼

核心代碼

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}class Solution {
public:int longestPalindrome(string word1, string word2) {string s = word1 + word2;const auto N1 = word1.length();const int N = s.length();vector<vector<int>> dp(N, vector<int>(N+1, 0));for (int i = 0; i < N; i++) {dp[i][i+1] = 1;}for (int len = 2; len <= N; len++) {for (int left = 0; left + len <= N; left++) {dp[left][left + len] = max(dp[left+1][left + len], dp[left][left + len-1]);if (s[left] == s[left + len - 1]) {MaxSelf(&dp[left][left + len], dp[left + 1][left + len - 1] + 2);}}}int iRet = 0;for (int i = 0; i < N1; i++) {for (int j = N1; j < N; j++) {if( s[i] == s[j]){ MaxSelf(&iRet, dp[i + 1][j] + 2); }				}}return iRet;}
};

單元測試用例

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{string word1,  word2;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod0){word1 = "cacb", word2 = "cbba";auto res = Solution().longestPalindrome(word1, word2);AssertEx(5, res);}TEST_METHOD(TestMethod1){word1 = "ab", word2 = "ab";auto res = Solution().longestPalindrome(word1, word2);AssertEx(3, res);}TEST_METHOD(TestMethod2){word1 = "aa", word2 = "bb";auto res = Solution().longestPalindrome(word1, word2);AssertEx(0, res);}TEST_METHOD(TestMethod3){word1 = "a", word2 = "a";auto res = Solution().longestPalindrome(word1, word2);AssertEx(2, res);}TEST_METHOD(TestMethod4){word1 = "rhuzwqohquamvsz", word2 = "kvunbxje";auto res = Solution().longestPalindrome(word1, word2);AssertEx(7, res);}TEST_METHOD(TestMethod5){word1 = "wqo", word2 = "hquamvs";auto res = Solution().longestPalindrome(word1, word2);AssertEx(3, res);}TEST_METHOD(TestMethod6){word1 = "wqo", word2 = "hq";auto res = Solution().longestPalindrome(word1, word2);AssertEx(3, res);}TEST_METHOD(TestMethod7){word1 = "qo", word2 = "hq";auto res = Solution().longestPalindrome(word1, word2);AssertEx(3, res);}TEST_METHOD(TestMethod8){word1 = "qo", word2 = "q";auto res = Solution().longestPalindrome(word1, word2);AssertEx(3, res);}};
}

擴展閱讀

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。