题目内容

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

题面描述

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

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

思路

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