LCS(Longest Common Subsequence) 问题即最长公共子序列问题,就是两个字符串的 子序列
而不是 子串
的最大的长度。
之前的 LIS 问题也可以通过构造两个字符串来解决,一个是原串,一个是排序后的递增串,然后通过两个字符串求 LCS 的问题。
算法流程
- 设定 dp[i][j] 为str(0…i) 与 patten(0…j) 的最长子公共子序列的长度
- 初始化 数组的 0 下标为零,然后更新 dp[i][j];
- 若
str[i] == patten[j]
则dp[i][j] = dp[i-1][j-1]
,若 str[i] != patten[j]
则 dp[i][j] = max(dp[i][j-1],dp[i-1][j])
- 迭代更新 dp[i][j]
最长子序列输出
- 若
str[i] == patten[j]
,则输出 str[i] (导致反向输出)
- 若
str[i] != patten[j]
,则判断 dp[i][j] 是等于上方的(i–)还是下方的(j–),然后移到该方向。
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
#include <iostream> #include <string> #include <algorithm>
using namespace std;
void lcs(const string &str, const string &patten) { const int strSize = str.length(); const int pattenSize = patten.length();
int dp[strSize+1][pattenSize+1] = {0};
for(int i = 1; i <= strSize; ++i) { for(int j = 1; j <= pattenSize; ++j) { if(str[i-1] == patten[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j],dp[i][j-1]); } } } int i = strSize; int j = pattenSize; vector<char> re; while(i > 0 && j > 0) { if(str[i-1] == patten[j-1]) { re.push_back(str[i-1]); --i; --j; } else if(dp[i][j] == dp[i-1][j]) { --i; } else if(dp[i][j] == dp[i][j-1]) { --j; } }
reverse(re.begin(),re.end()); for(auto c:re) { cout<<c; } cout<<endl;
}
int main(int argc, char *argv[]) { string str = "kangqingfei"; string patten = "ng";
lcs(str,patten);
return 0; }
|
编辑距离问题(Edit Distance)
编辑距离和LCS很像,只是更新 dp[i][j] 的时候略有不同而已
算法流程
- 设定 dp[i][j] 为 str1(0…i) 与 str2(0…j) 的编辑距离
- 初始化 dp[0][j] 和 dp[i][0] 为 j 和 i 其含义为,一个字符串与一个空串的编辑距离为字符串本身的长度
- 更新dp[i][j],更新规则为,若 str1[i] == str2[j] 则dp[i][j] = dp[i-1][j-1] 若 str1[i] != str2[j] 则考虑 str1 不变,str2 可以通过 增加(dp[i-1][j] + 1) 删除(dp[i][j-1] + 1) 替换(dp[i-1][j-1] + 1) 变到str1
- 迭代更新 dp[i][j], 输出dp[iMax][jMax] 即为编辑距离
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <iostream> #include <string> #include <algorithm>
using namespace std;
editDistance(string str1, string str2) { const int length1 = str1.length(); const int length2 = str2.length();
int dp[length1+1][length2+1] = {0};
for(int i = 0; i <= length1; ++i) { dp[i][0] = i; } for(int i = 0; i <= length2; ++i) { dp[0][i] = i; } for(int i = 0; i <= length1; ++i) { for(int j = 0; j <= length2; ++j) { if(str1[i] == str2[j]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1; } } } cout<<dp[length1][length2]<<endl;
}
int main(int argc, char *argv[]) { string str1 = "kangqingfei"; string str2 = "kangqingfeng";
editDistance(str1,str2);
return 0; }
|
最长公共子串问题
该问题与 LCS 问题的区别就在于 是否连续
若可以连续就是子串
否则就是子序列
。
对于子串的解法与子序列的解法基本一致 区别就在于
1 2 3 4
| if(str1[i] != str2[j]) dp[i][j] = 0 else if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1]+1
|
最后通过 遍历 dp[i][j] 来获得最大的子串长度,然后得到子串
在空间优化上面可以通过滚动数组来节省空间
最大连续序列求和(Maximum Contiguous Subsequence Sum)MCSS 问题
该问题为求一个序列的所有子序列中 和最大 的那个子序列。
该问题为简单的动态规划问题
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include <iostream> #include <vector>
using namespace std;
int mcss(vector<int> &arr) { const int len = arr.size()+1; int dp[len]; int maxSum = 0; dp[0] = 0; for(int i = 1; i < len; ++i) { dp[i] = dp[i-1] > 0 ? arr[i-1]+dp[i-1]:arr[i-1]; if(dp[i] > maxSum) maxSum = dp[i]; } return maxSum;
}
int mcssPlus(vector<int> &arr) { int maxSum = 0; int tmpDp = 0; for(int i = 0; i < arr.size(); ++i) { if(tmpDp > 0) { tmpDp += arr[i]; } else { tmpDp = arr[i]; } if(tmpDp > maxSum) maxSum = tmpDp; }
return maxSum; }
int main(int argc, char *argv[]) { int count,tmp; vector<int> arr; cin>>count; while(count--) { cin>>tmp; arr.push_back(tmp); }
cout<<mcssPlus(arr);
return 0; }
|