题面描述

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

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

思路

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

题目内容

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