题面描述

给定两个字符串 $A$ 和 $B$，我们需要计算从原点 $(0,0)$ 到终点 $(m,n)$ 的最短路径。其中，$m$ 和 $n$ 分别是字符串 $A$ 和 $B$ 的长度。路径的规则如下：

1. 水平边和垂直边的距离为 $1$。
2. 如果两个字符串在相同位置的字符相同，则可以走斜边，斜边的距离也为 $1$。

思路

这个问题可以转化为一个典型的动态规划问题。我们可以使用一个二维数组 dp[i][j] 来表示从 $(0,0)$ 到 $(i,j)$ 的最短路径长度。

• 如果 $A[i-1] == B[j-1]$，那么我们可以从 $(i-1, j-1)$ 走斜边到达 $(i,j)$，此时 dp[i][j] = dp[i-1][j-1] + 1。
• 否则，我们只能从 $(i-1, j)$ 或 $(i, j-1)$ 走水平或垂直边到达 $(i,j)$，此时 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。

最终，dp[m][n] 即为所求的最短路径长度。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int shortestPath(string A, string B) {
    int m = A.length();
    int n = B.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // 初始化边界条件
    for (int i = 1; i <= m; ++i) {
        dp[i][0] = i;  // 只能走垂直边
    }
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = j;  // 只能走水平边
    }

    // 填充dp表
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;  // 走斜边
            } else {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;  // 走水平或垂直边
            }
        }
    }

    return dp[m][n];
}

int main() {
    string A, B;
    cin >> A >> B;
    cout << shortestPath(A, B) << endl;
    return 0;
}

python

def shortest_path(A, B):
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界条件
    for i in range(1, m + 1):
        dp[i][0] = i  # 只能走垂直边
    for j in range(1, n + 1):
        dp[0][j] = j  # 只能走水平边

    # 填充dp表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1  # 走斜边
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1  # 走水平或垂直边

    return dp[m][n]

# 输入
A, B = input().split()
# 输出
print(shortest_path(A, B))

java

import java.util.Scanner;

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

        // 初始化边界条件
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;  // 只能走垂直边
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;  // 只能走水平边
        }

        // 填充dp表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;  // 走斜边
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;  // 走水平或垂直边
                }
            }
        }

        return dp[m][n];
    }

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

题目内容

给定两个字符串，分别为字符串 $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$。

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

输入描述

空格分割的两个字符串 $A$ 与字符串 $B$

• 字符串不为"空串"

• 字符格式满足正则规则：$[A-Z]$

• 字符串长度 $< 10000$

输出描述

原点到终点的最短距离

样例1

输入

ABC ABC

输出

3

样例2

输入

ABCABBA CBABAC

输出

9