华为OD统一考试 - 两个字符串间的最短路径问题

题目描述

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

输出描述

原点到终点的最短距离

用例

题目解析

本题可以通过动态规划来求解：

我们假设dp[i][j]表示(0,0)到(i,j)的最短距离，那么这个最短距离只可能来自三个方向：

• dp[i-1][j]，当前点的上方点
• dp[i][j-1]，当前点的左边点
• dp[i-1][j-1]，当前点的左上方点

而存在推导式如下：

dp[i][j] = min(dp[i-1][j]，dp[i][j-1]，dp[i-1][j-1]) + 1

另外需要注意的是，上面推导式dp[i-1][j-1]参与比较是有前提条件的，即如果(i-1, j-1)点和(i,j)点之间存在斜线相连时，才能将dp[i-1][j-1]带入上面推导式，否则不能带入。

并且上面推导式还可以优化，如果当前点可以向三个方向扩散：

• 向右
• 向下
• 向右下

那么向右和向下是否有必要扩散呢？比如下图

从(1,1)处可以向三个方向扩散，此时可以看出扩散后的三个新位置X,Y,Z，其中Y要比X,Z更靠近右下角点。

那么有没有可能存在一种路径，比如Z点沿着这条路径到达右下角点更快呢？我们改造一下上面图示：

假设存在下面路径，可以让Z点快速到达右下角点，此时我们可以发现，其实Y点也可以凭借该路径以一样的路径长度到达

因此，如果如果存在一条路径可以让Z快速到达右下角点，那么Y一定也可以借用到这条路径，以一样的距离到达右下角点。再给个图