04.06_双序列问题
双序列问题
问题描述
双序列动态规划是指在两个序列上进行状态转移的问题。
常见的有最长公共子序列(LCS)、编辑距离等。
通常需要定义状态表示两个序列某个位置的最优解。
最长公共子序列(LCS)
算法思想
- 定义dp[i][j]表示s1的前i个字符和s2的前j个字符的LCS长度
- 如果s1[i] == s2[j]，则可以选择该字符作为LCS的一部分
- 状态转移方程：
- 当s1[i] == s2[j]时：dp[i][j] = dp[i-1][j-1] + 1
- 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 最终答案为dp[n][m]
代码实现
int longestCommonSubsequence(string s1, string s2) {
int n = s1.length(), m = s2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n][m];
}
public int longestCommonSubsequence(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[n][m];
}
def longestCommonSubsequence(s1: str, s2: str) -> int:
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[n][m]
编辑距离
算法思想
- 定义dp[i][j]表示将s1的前i个字符转换为s2的前j个字符所需的最小操作数
- 每次可以进行插入、删除或替换操作
- 状态转移方程：
- 当s1[i] == s2[j]时：dp[i][j] = dp[i-1][j-1]
- 否则：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
- 最终答案为dp[n][m]
代码实现
int minDistance(string s1, string s2) {
int n = s1.length(), m = s2.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
// 初始化边界
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;
}
}
}
return dp[n][m];
}
public int minDistance(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];
// 初始化边界
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]),
dp[i][j-1]) + 1;
}
}
}
return dp[n][m];
}
def minDistance(s1: str, s2: str) -> int:
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 初始化边界
for i in range(n + 1):
dp[i][0] = i
for j in range(m + 1):
dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
return dp[n][m]
时间复杂度分析
算法 时间复杂度 空间复杂度| 最长公共子序列 | ||
| 编辑距离 |
应用场景
- 序列比较
- 文本相似度
- DNA序列分析
- 拼写检查
- 版本控制差异
注意事项
- 状态定义的选择
- 边界条件的处理
- 空间优化的可能性
- 路径还原的需求
- 初始化的正确性