2024华为OD机试真题-两个字符串间的最短路径-C卷D卷-200分-(C++/Python)

 2024华为OD机试题库-(C卷+D卷)-(JAVA、Python、C++)

题目描述

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

说明

无

考点

动态规划

解题思路

本题可以用动态规划去求解，到达(m,n)点可以从(m-1,n),(m,n-1),(m-1,n-1)三种选择，

dp(i,j)表示从(0,0)到达(i,j)点要走的最短路径，则状态转移方程可以表示为：dp(i,j)=

min(dp(i-1,j),dp(i,j-1),dp(i-1,j-1))+1；但上一步是(i-1,j-1)也是有条件的，即

A[j-1]==B[i-1]时才可以。因此，在满足A[j-1]==B[i-1]时，dp(i,j)=dp(i-1,j-1)+1;

不满足A[j-1]==B[i-1]时，dp(i,j)=min(dp(i-1,j),dp(i,j-1))+1

代码

c++