3397: 【DP】2024D-两个字符串间的最短路径
金币值：
1
时间限制：2.000 s
内存限制：128 M
正确：254
提交：486
正确率：52.26% 命题人：
题目描述
给定两个字符串，分别为字符串
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
输出格式
原点到终点的最短距离
输入样例 复制
ABC ABC输出样例 复制
3