https://leetcode.cn/problems/longest-common-subsequence/description/?envType=problem-list-v2&envId=dynamic-programming
ref https://leetcode.cn/problems/longest-common-subsequence/solutions/2133188/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-lbz5
| ”” | a | c | e | |
|---|---|---|---|---|
| ”” | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 |
| b | 0 | 1 | 1 | 1 |
| c | 0 | 1 | 2 | 2 |
| d | 0 | 1 | 2 | 2 |
| e | 0 | 1 | 2 | 3 |
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// s[1:m] 和 t[1:n]的 lcs
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
// 可以找 dp[i-1][j-1]但是没必要, 因为这个值不可能比 i,j-1和 i-1,j还大
}
}
}
return dp[m][n];
}
};
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<int> dp(n + 1, 0), dp1(n + 1, 0);
bool flg{};
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
if (flg)
dp1[j] = dp[j - 1] + 1; // 第二轮
else
dp[j] = dp1[j - 1] + 1; // 第一轮
} else {
if (flg)
dp1[j] = max(dp1[j - 1], dp[j]);
else
dp[j] = max(dp[j - 1], dp1[j]);
}
}
flg = !flg;
}
// 首轮是 false(i=1) 所以最后一轮需要看 m 的奇偶性
// 假设只有两轮, 结果是 dp1[n]. 所以 m 是偶数的话读取 dp1 的值
return (m & 1) ? dp[n] : dp1[n];
}
};
但是写法不够优雅. 可以用求余的方式做. 比较直观
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dp(2, vector<int>(n + 1, 0));
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + 1;
} else {
dp[i & 1][j] = max(dp[i & 1][j - 1], dp[(i - 1) & 1][j]);
}
}
}
// 首轮是(i=1) 所以最后一轮需要看 m 的奇偶性
// 假设只有两轮, 结果是 dp[2&1][n]. 所以第 m 轮是 dp[m&1]
return dp[m & 1][n];
}
};
还有一种很优雅的单数组写法, 需要注意状态的转移
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<int> dp(n + 1, 0);
for (int i = 1; i <= m; ++i) { // s
for (int j = 1, pre = 0; j <= n; ++j) { // t
int tmp = dp[j];
if (s[i - 1] == t[j - 1]) {
dp[j] = pre + 1;
} else {
dp[j] = max(dp[j - 1], dp[j]);
}
pre = tmp;
}
}
return dp[n];
}
};
可以用 for-range 来做. 最优雅的写法
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<int> dp(n + 1, 0);
for (auto c : s) { // s
for (int j = 1, pre = 0; j <= n; ++j) { // t
int tmp = dp[j];
if (c == t[j - 1]) {
dp[j] = pre + 1;
} else {
dp[j] = max(dp[j - 1], dp[j]);
}
pre = tmp;
}
}
return dp[n];
}
};
扩展: 怎么找最长公共子序列
需要回溯遍历之前的最优路径.
class Solution {
public:
int longestCommonSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// s[1:m] 和 t[1:n]的 lcs
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
string lcs;
for (int i{m}, j{n}; i > 0 && j > 0;) {
if (s[i - 1] == t[j - 1]) {
lcs += (s[i - 1]);
--i, --j;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
--i;
} else {
--j;
}
}
reverse(lcs.begin(), lcs.end());
cout << lcs << '\n';
return dp[m][n];
}
};