🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

✨ 两个字符串间的最短路径

问题描述

给定两个字符串 $A$ 和 $B$。例如，字符串 $A$ 为 “ABCABBA”，字符串 $B$ 为 “CBABAC”。可以构建一个大小为 $m\times n$ 的二维数组，其中 $m$ 为字符串 $A$ 的长度，$n$ 为字符串 $B$ 的长度。定义二维数组的原点为 $(0,0)$，终点为 $(m,n)$。在数组中，水平和垂直的每条边的距离为 1，如果字符串 $A$ 和字符串 $B$ 在相同位置的字符相同，则可以画一条斜边，斜边的距离同样为 1。

例如，从 $(0,0)$ 到 $(0,A)$ 是水平边，距离为 1；从 $(0,A)$ 到 $(A,C)$ 是垂直边，距离为 1。如果两个字符串在相同位置的字符相同，例如 $(A,C)$ 到 $(B,B)$，则可以画一条斜边，距离为 1。这样，原点 $(0,0)$ 到终点 $(m,n)$ 的最短路径包括水平边、垂直边和斜边。

输入格式

第一行包含两个用空格分隔的字符串 $A$ 和 $B$，字符串不为空，字符格式满足正则规则：[A-Z]，且字符串长度 $\le 10000$。

输出格式

输出从原点 $(0,0)$ 到终点 $(m,n)$ 的最短路径距离。

样例输入

输入1

ABC ABC

输入2

ABCABBA CBABAC

样例输出

输出1

3

输出2

9

样例解释

对于输入 “ABC” 和 “ABC”，可以画出以下路径：

(0,0) -> (A,0) -> (A,A) -> (B,B) -> (C,C)

对于输入 “ABCABBA” 和 “CBABAC”，最短路径如下图红线标记，最短距离为 9：

(0,0) -> (A,0) -> (A,C) -> (B,B) -> (C,B) -> (A,A) -> (B,B) -> (B,B) -> (A,A) -> (A,C)

数据范围

字符串长度 $\le 10000$。

题解

我们可以使用动态规划来解决这个问题。定义一个二维数组 $dp$，其中 $dp[i][j]$ 表示从原点 $(0,0)$ 到 $(i,j)$ 的最短距离。初始化时，$dp[0][0]=0$，然后根据以下规则进行状态转移：

1. 如果 $i>0$，则 $dp[i][j]=\min (dp[i][j],dp[i-1][j]+1)$。
2. 如果 $j>0$，则 $dp[i][j]=\min (dp[i][j],dp[i][j-1]+1)$。
3. 如果 $i>0$ 且 $j>0$ 且 $A[i-1]==B[j-1]$，则 $dp[i][j]=\min (dp[i][j],dp[i-1][j-1]+1)$。

最后，$dp[m][n]$ 即为所求的最短路径距离。

参考代码

• Python

def min_distance(A, B):
    m, n = len(A), len(B)
    dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = 0
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
            if i > 0 and j > 0 and A[i - 1] == B[j - 1]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
    
    return dp[m][n]

A, B = input().split()
print(min_distance(A, B))

• Java

import java.util.Scanner;

public class Main {
    public static int minDistance(String A, String B) {
        int m = A.length();
        int n = B.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        dp[0][0] = 0;

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0) dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
                if (j > 0) dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                if (i > 0 && j > 0 && A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        System.out.println(minDistance(A, B));
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    int m = A.size(), n = B.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
    dp[0][0] = 0;

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
            if (i > 0 && j > 0 && A[i - 1] == B[j - 1]) {
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }

    cout << dp[m][n] << endl;
    return 0;
}