华为OD机试 - 两个字符串间的最短路径问题 - 动态规划（Java 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

2、输出

3、说明

四、解题思路

根据题目描述，我们可以得出以下状态转移方程：

如果A的第i个字符等于B的第j个字符，那么 dp[i][j] = dp[i-1][j-1]，即可以通过斜边直接到达，距离不变。
如果A的第i个字符不等于B的第j个字符，那么 dp[i][j] 可以通过水平或垂直边到达。我们取 dp[i-1][j] 和 dp[i][j-1] 中的最小值，然后加1，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。
然后，我们从左上角开始遍历数组，根据状态转移方程逐步填充 dp 数组，最终得到原点到终点的最短距离。

五、Java算法源码

public class OdTest01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] arr = sc.nextLine().split(" ");
        String A = arr[0];
        String B = arr[1];
        int result = shortestDistance(A, B);
        System.out.println(result);
    }

    public static int shortestDistance(String A, String B) {
        int m = A.length();
        int n = B.length();
        // 定义dp数组，表示从原点到每个点的最短距离
        int[][] dp = new int[m + 1][n + 1];

        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i; // 初始化水平边距离
        }
        for (int j = 0; 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 {
                    // 字符不同，取水平和垂直边距离的最小值，加1
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }

        // 返回原点到终点的最短距离
        return dp[m][n];
    }
}