【区间动态规划】1771. 由子序列构造的最长回文串的长度

本文涉及知识点

动态规划汇总

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)
$=\begin{cases} 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{cases}$

动态规划的初值值

长度为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

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛