跳至主要內容

【DP】2024D-两个字符串间的最短路径

【DP】2024D-两个字符串间的最短路径

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3397

题目描述

给定两个字符串，分别为字符串A与字符串B。

例如A字符串为ABCABBA，B字符串为CBABAC，可以得到下图m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图。

从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1；假设两个字符串同一位置的两个字符相同则可以作一个斜边，如(A,C)到(B,B)最短距离为斜边，距离同样为1。出所有的斜边如下图，(0,0)到(B,B)的距离为 1个水平边+ 1个垂直边+ 1个斜边=3。

img
img

根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9

img
img

输入描述

空格分割的两个字符串A与字符串B，字符串不为空串，字符格式满足正则规则:[A-Z]，字符串长度<10000

输出描述

原点到终点的最短距离

示例一

输入

ABC ABC

输出

3

示例二

输入

ABCABBA CBABAC

输出

9

解题思路

如果我们把问题看作是一个类似于LeetCode 62、不同路径 的经典二维路径dp问题，可以注意到如下图所示

img
img

每一个点(i, j)可能可以从其左边(i, j-1)，上边(i-1, j)，左上(i-1, j-1)转移过来。

其中i和j分别表示第一个字符串s1和第二个字符串s2中的第i个和第j个字符。

换言之，如果抛开字符串相关部分不看，而是建立一个连接了若干斜边的二维网格，那么问题则转化为了类似LeetCode 62、不同路径 的dp问题，只不过存在若干可以斜着走的路径。

我们考虑动态规划三部曲

  1. dp数组的含义是什么？

可以从两个角度来思考这个问题。

  1. 类似于LeetCode 62、不同路径 的经典二维路径dp问题，从二维网格中的路径转移的角度出发。
  2. 类似于LeetCode 1143、最长公共子序列 、LeetCode 72、编辑距离 等的经典双字符串dp问题，从需要同时考虑两个字符串的子串的角度出发。

显然需要构建的dp数组是一个二维的dp数组。

构建大小为(n+1)*(m+1)的二维dp数组。

dp[i][j]表示考虑子串s1[:i]和子串s2[:j]，它们之间的最短路径。特别地，当 i = 0 或 j = 0 时表示子串为空串。

  1. 动态转移方程是什么？

需要讨论两个子串最后一个字符s1[i-1]和s2[j-1]之间是否相等。若

  • s1[i-1] == s2[j-1]，则可以从左边、上边、左上边转移过来
  • s1[i-1] != s2[j-1]，则只可以从左边、上边转移过来

核心代码为

if s1[i-1] == s2[j-1]:
    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
else:
    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

其中+1表示无论从哪一个状态转移过来，都需要加上1的距离。

  1. dp数组如何初始化？

主要是分别考虑 i = 0 和 j = 0 的空串情况。

以 i = 0 为例（j = 0类似），dp[0][j]表示考虑空串""和s2的子串s2[:j]之间的最短距离。

从图上也可以看出，这个距离显然为j。故初始化的代码如下

for i in range(1, n+1):
    dp[i][0] = i
for j in range(1, m+1):
    dp[0][j] = j

代码

Python

# 题目：【DP】2023C-两个字符串间的最短路径
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：DP
# 代码看不懂的地方，请直接在群上提问


# 输入s1, s2两个字符串
s1, s2 = input().split()
# 获得两个字符串的长度
n, m = len(s1), len(s2)

# dp数组的初始化
# 构建大小为(n+1)*(m+1)的二维dp数组
# dp[i][j]表示考虑子串s1[:i]和子串s2[:j]
# 它们之间的最短路径
# 特别地，当 i = 0 或 j = 0 时表示空串
dp = [[0] * (m+1) for _ in range(n+1)]

# 设置dp[i][0]为i，表示取s2子串为空串""，和取s1的子串s1[:i]
# 之间的最短路径为i
for i in range(1, n+1):
    dp[i][0] = i
# 设置dp[0][j]为j，表示取s1子串为空串""，和取s2的子串s2[:j]
# 之间的最短路径为j
for j in range(1, m+1):
    dp[0][j] = j


# 双重遍历每一个点(i,j)
# 考虑子串s1[:i]和s2[:j]
for i in range(1, n+1):
    for j in range(1, m+1):
        # 考两个子串的最后一个字符s1[i-1]和s2[j-1]
        # 若相等，则可以从左上角dp[i-1][j-1]转移过来
        if s1[i-1] == s2[j-1]:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        # 若不相等，则只能从左边或者上边转移过来
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1

# 输出dp[n][m]
# 表示s1[:n]和s2[:m]的最短路径
# 即为s1和s2的最短路径
print(dp[n][m])

Java

import java.util.Scanner;  
  
public class Main {  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        String s1 = scanner.next();  
        String s2 = scanner.next();  
        scanner.close();  
  
        int n = s1.length();  
        int m = s2.length();  
  
        // dp数组的初始化  
        // 构建大小为(n+1)*(m+1)的二维dp数组  
        // dp[i][j]表示考虑子串s1[:i]和子串s2[:j]  
        // 它们之间的最短路径  
        int[][] dp = new int[n + 1][m + 1];  
  
        // 设置dp[i][0]为i，表示取s2子串为空串""，和取s1的子串s1[:i]  
        // 之间的最短路径为i  
        for (int i = 1; i <= n; i++) {  
            dp[i][0] = i;  
        }  
  
        // 设置dp[0][j]为j，表示取s1子串为空串""，和取s2的子串s2[:j]  
        // 之间的最短路径为j  
        for (int j = 1; j <= m; j++) {  
            dp[0][j] = j;  
        }  
  
        // 双重遍历每一个点(i,j)  
        // 考虑子串s1[:i]和s2[:j]  
        for (int i = 1; i <= n; i++) {  
            for (int j = 1; j <= m; j++) {  
                // 考察两个子串的最后一个字符s1[i-1]和s2[j-1]  
                // 若相等，则可以从左上角dp[i-1][j-1]转移过来  
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {  
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;  
                }  
                // 若不相等，则只能从左边或者上边转移过来  
                else {  
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;  
                }  
            }  
        }  
  
        // 输出dp[n][m]  
        // 表示s1[:n]和s2[:m]的最短路径  
        // 即为s1和s2的最短路径  
        System.out.println(dp[n][m]);  
    }  
}

C++

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    std::string s1, s2;  
    std::cin >> s1 >> s2;  
  
    int n = s1.length();  
    int m = s2.length();  
  
    // dp数组的初始化  
    // 构建大小为(n+1)*(m+1)的二维dp数组  
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));  
  
    // 设置dp[i][0]为i，表示取s2子串为空串""，和取s1的子串s1[:i]  
    // 之间的最短路径为i  
    for (int i = 1; i <= n; ++i) {  
        dp[i][0] = i;  
    }  
  
    // 设置dp[0][j]为j，表示取s1子串为空串""，和取s2的子串s2[:j]  
    // 之间的最短路径为j  
    for (int j = 1; j <= m; ++j) {  
        dp[0][j] = j;  
    }  
  
    // 双重遍历每一个点(i,j)  
    // 考虑子串s1[:i]和s2[:j]  
    for (int i = 1; i <= n; ++i) {  
        for (int j = 1; j <= m; ++j) {  
            // 考察两个子串的最后一个字符s1[i-1]和s2[j-1]  
            // 若相等，则可以从左上角dp[i-1][j-1]转移过来  
            if (s1[i - 1] == s2[j - 1]) {  
                dp[i][j] = std::min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;  
            }  
            // 若不相等，则只能从左边或者上边转移过来  
            else {  
                dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + 1;  
            }  
        }  
    }  
  
    // 输出dp[n][m]  
    // 表示s1[:n]和s2[:m]的最短路径  
    // 即为s1和s2的最短路径  
    std::cout << dp[n][m] << std::endl;  
  
    return 0;  
}

时空复杂度

时间复杂度：O(NM)。dp过程，双重循环所需时间复杂度。

空间复杂度：O(NM)。二维dp数组所占空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法