Related: Longest Common Subsequence
https://www.lintcode.com/problem/longest-common-subsequence-ii/description
https://www.geeksforgeeks.org/longest-common-subsequence-with-at-most-k-changes-allowed/
https://www.jiuzhang.com/solution/longest-common-subsequence-ii/
最长公共子串的问题是典型的动态规划题，在这里已有题解，就是用二维矩阵来存储所有的中间最佳状态。
这是这个题的变种，因为第一个字符串可以进行k次变动。那么解体就得用三维矩阵来存储中间最佳状态。
而且要把k=0的情况拿出来单独解决。这个k=0的情况实际上就是无变动情形下的解。这个的时间复杂度
是O(mnk)，m和n是P和Q字符串的长度，k是P可变换元素数量。
https://blog.csdn.net/zhaohengchuan/article/details/79703980
dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度。初始化之后，对于dp[i][j][t]，如果P[i-1]=Q[j-1]，由于t表示改变t个元素，dp[i][j][t]可能取dp[i-1][j-1][t]+1，在P[i-1]!=Q[j-1]时，dp[i][j][t]可能取dp[i-1][j-1][t-1]+1（需要改变一个元素）。由于dp[i][j][t]还可能取dp[i-1][j][t]和dp[i][j-1][t]，最终结果取最大值。
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
if (P.empty() || Q.empty() || k < 0)
return 0;
int lenp = P.size(), lenq = Q.size();
//dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度
vector<vector<vector<int>>> dp(lenp + 1, vector<vector<int>>(lenq + 1, vector<int>(k + 1)));
//当i = 0或j = 0时,dp[i][j][t] = 0
for (int i = 0; i <= lenp; ++i)
{
for (int t = 0; t <= k; ++t)
dp[i][0][t] = 0;
}
for (int j = 0; j <= lenq; ++j)
{
for (int t = 0; t <= k; ++t)
dp[0][j][t] = 0;
}
//处理k=0的情况,类似于公共子序列
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][0] = dp[i - 1][j - 1][0] + 1;
else
dp[i][j][0] = maxVal(dp[i - 1][j][0], dp[i][j - 1][0]);
}
}
//若P[i-1]=Q[j-1],不必再变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t]+1的最大值
//否则,可能需要变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t-1]+1的最大值
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
for (int t = 1; t <= k; ++t)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t] + 1));
else
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t - 1] + 1));
}
}
}
return dp[lenp][lenq][k];
}
https://github.com/jiadaizhao/LintCode/blob/master/0762-Longest%20Common%20Subsequence%20II/0762-Longest%20Common%20Subsequence%20II.cpp
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
int m = P.size();
int n = Q.size();
int dp[1 + k][1 + m][1 + n];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[0][i][j] = 1 + dp[0][i - 1][j - 1];
}
else {
dp[0][i][j] = max(dp[0][i - 1][j], dp[0][i][j - 1]);
}
}
}
for (int l = 1; l <= k; ++l) {
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[l][i][j] = 1 + dp[l][i - 1][j - 1];
}
else {
dp[l][i][j] = max({dp[l][i - 1][j], dp[l][i][j - 1], 1 + dp[l - 1][i - 1][j - 1]});
}
}
}
}
return dp[k][m][n];
}
https://www.lintcode.com/problem/longest-common-subsequence-ii/description
Given two sequence
P and Q of numbers. The task is to find Longest Common Subsequence of two sequence if we are allowed to change at most k element in first sequence to any value.Example
Given P =
Return
[8 ,3], Q = [1, 3], K = 1Return
2
Given P =
Return
[1, 2, 3, 4, 5], Q = [5, 3, 1, 4, 2], K = 1Return
3
The idea is to use Dynamic Programming. Define a 3D matrix dp[][][], where dp[i][j][k] defines the Longest Common Subsequence for the first i numbers of first array, first j number of second array when we are allowed to change at max k number in the first array.
Therefore, recursion will look like
Therefore, recursion will look like
If P[i] != Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k - 1] + 1)
If P[i] == Q[j],
dp[i][j][k] = max(dp[i - 1][j][k],
dp[i][j - 1][k],
dp[i - 1][j - 1][k] + 1)
Time Complexity: O(N*M*K).
最长公共子串的问题是典型的动态规划题，在这里已有题解，就是用二维矩阵来存储所有的中间最佳状态。
这是这个题的变种，因为第一个字符串可以进行k次变动。那么解体就得用三维矩阵来存储中间最佳状态。
而且要把k=0的情况拿出来单独解决。这个k=0的情况实际上就是无变动情形下的解。这个的时间复杂度
是O(mnk)，m和n是P和Q字符串的长度，k是P可变换元素数量。
def longestCommonSubsequence2(self, P, Q, k):
# Write your code here
m = len(P)
n = len(Q)
l = [[[None for g in range(k+1)] \
for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0:
l[i][j][0] = 0
elif P[i-1] == Q[j-1]:
l[i][j][0] = l[i-1][j-1][0] + 1
else:
l[i][j][0] = max(l[i-1][j][0], l[i][j-1][0])
for i in range(m+1):
for j in range(n+1):
for g in range(1, k+1):
if i == 0 or j == 0:
l[i][j][g] = 0
elif P[i-1] != Q[j-1]:
l[i][j][g] = max(l[i-1][j][g], l[i][j-1][g], l[i-1][j-1][g-1] + 1)
else:
l[i][j][g] = max(l[i-1][j][g], l[i][j-1][g], l[i-1][j-1][g] + 1)
return l[m][n][k]https://blog.csdn.net/zhaohengchuan/article/details/79703980
dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度。初始化之后，对于dp[i][j][t]，如果P[i-1]=Q[j-1]，由于t表示改变t个元素，dp[i][j][t]可能取dp[i-1][j-1][t]+1，在P[i-1]!=Q[j-1]时，dp[i][j][t]可能取dp[i-1][j-1][t-1]+1（需要改变一个元素）。由于dp[i][j][t]还可能取dp[i-1][j][t]和dp[i][j-1][t]，最终结果取最大值。
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
if (P.empty() || Q.empty() || k < 0)
return 0;
int lenp = P.size(), lenq = Q.size();
//dp[i][j][t]表示P的前i个数字和Q的前j个数字中,在变换了t个元素的情况下,最长公共子序列的长度
vector<vector<vector<int>>> dp(lenp + 1, vector<vector<int>>(lenq + 1, vector<int>(k + 1)));
//当i = 0或j = 0时,dp[i][j][t] = 0
for (int i = 0; i <= lenp; ++i)
{
for (int t = 0; t <= k; ++t)
dp[i][0][t] = 0;
}
for (int j = 0; j <= lenq; ++j)
{
for (int t = 0; t <= k; ++t)
dp[0][j][t] = 0;
}
//处理k=0的情况,类似于公共子序列
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][0] = dp[i - 1][j - 1][0] + 1;
else
dp[i][j][0] = maxVal(dp[i - 1][j][0], dp[i][j - 1][0]);
}
}
//若P[i-1]=Q[j-1],不必再变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t]+1的最大值
//否则,可能需要变换元素,dp[i][j][t]是dp[i-1][j][t],dp[i][j-1][t],dp[i-1][j-1][t-1]+1的最大值
for (int i = 1; i <= lenp; ++i)
{
for (int j = 1; j <= lenq; ++j)
{
for (int t = 1; t <= k; ++t)
{
if (P[i - 1] == Q[j - 1])
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t] + 1));
else
dp[i][j][t] = maxVal(dp[i - 1][j][t], maxVal(dp[i][j - 1][t], dp[i - 1][j - 1][t - 1] + 1));
}
}
}
return dp[lenp][lenq][k];
}
https://github.com/jiadaizhao/LintCode/blob/master/0762-Longest%20Common%20Subsequence%20II/0762-Longest%20Common%20Subsequence%20II.cpp
int longestCommonSubsequence2(vector<int> &P, vector<int> &Q, int k) {
// Write your code here
int m = P.size();
int n = Q.size();
int dp[1 + k][1 + m][1 + n];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[0][i][j] = 1 + dp[0][i - 1][j - 1];
}
else {
dp[0][i][j] = max(dp[0][i - 1][j], dp[0][i][j - 1]);
}
}
}
for (int l = 1; l <= k; ++l) {
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (P[i - 1] == Q[j - 1]) {
dp[l][i][j] = 1 + dp[l][i - 1][j - 1];
}
else {
dp[l][i][j] = max({dp[l][i - 1][j], dp[l][i][j - 1], 1 + dp[l - 1][i - 1][j - 1]});
}
}
}
}
return dp[k][m][n];
}
