【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【DP】2024D-两个字符串间的最短路径【欧弟算法】全网注释最详细分类最全的华为OD真题题解

有LeetCode算法/华为OD考试扣扣交流群可加 948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

• 题目描述与示例
• • 题目描述
  • 输入描述
  • 输出描述
  • 示例一
  • • 输入
    • 输出
    • 示例二
    • • 输入
      • 输出
      • 解题思路
      • 代码
      • • python
        • Java
        • C++
        • 时空复杂度
        • 华为OD算法/大厂面试高频题算法练习冲刺训练

          从2024年4月15号开始，OD机考全部配置为2024D卷。

          注意两个关键点：

          1. 会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
          2. 现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

          题目描述与示例

          题目描述

          给定两个字符串，分别为字符串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]，字符串长度 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 dp[i][0] = i; } // 设置dp[0][j]为j，表示取s1子串为空串""，和取s2的子串s2[:j] // 之间的最短路径为j for (int j = 1; j dp[0][j] = j; } // 双重遍历每一个点(i,j) // 考虑子串s1[:i]和s2[:j] for (int i = 1; i for (int j = 1; 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]); } } std::string s1, s2; std::cin s1 s2; int n = s1.length(); int m = s2.length(); // dp数组的初始化 // 构建大小为(n+1)*(m+1)的二维dp数组 std::vector dp[i][0] = i; } // 设置dp[0][j]为j，表示取s1子串为空串""，和取s2的子串s2[:j] // 之间的最短路径为j for (int j = 1; j dp[0][j] = j; } // 双重遍历每一个点(i,j) // 考虑子串s1[:i]和s2[:j] for (int i = 1; i for (int j = 1; 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