刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！
简答题
4.字母游戏
一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？
时间限制：6000
内存限制：65536
输入
输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg
goodmorning
样例输出
8
提示
样例解释：
1、 从 iononmrogdg 开始；
2、 将最后一个 g 移动到串头: giononmrogd；
3、 将 m 移动到串尾: giononrogdm；
4、 将第一个 o 移动到串尾: ginonrogdmo；
5、 将 r 移动到串尾: ginonogdmor；
6、 将第一个 n 移动到串尾: gionogdmorn；
7、 将 i 移动到串尾: gonogdmorni；
8、 将第一个 n 移动到串尾: googdmornin；
9、 将第二个 g 移动到串尾: goodmorning。
一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T。两个串包含有同样的字母，只是顺序不同。换句话说，将 S 中的字母重排顺序就可以得到 T。游戏的每一步，我们可以将 S 中的任一字母移动到串头或串尾，问将 S 变换成 T 至少需要多少步？
时间限制：6000
内存限制：65536
输入
输入分两行，先后给出字母串 S 和 T。如题面所描述的，两者包含同样的小写英文字母，只是顺序不同。每个字母串的长度不超过 1000。
输出
在一行中输出将 S 变换成 T 至少需要的步骤数。
样例输入
iononmrogdg
goodmorning
样例输出
8
提示
样例解释：
1、 从 iononmrogdg 开始；
2、 将最后一个 g 移动到串头: giononmrogd；
3、 将 m 移动到串尾: giononrogdm；
4、 将第一个 o 移动到串尾: ginonrogdmo；
5、 将 r 移动到串尾: ginonogdmor；
6、 将第一个 n 移动到串尾: gionogdmorn；
7、 将 i 移动到串尾: gonogdmorni；
8、 将第一个 n 移动到串尾: googdmornin；
9、 将第二个 g 移动到串尾: goodmorning。
使用微信搜索喵呜刷题，轻松应对考试！
答案：
解析：
{这个问题可以通过动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示将字符串S的前i个字符变成字符串T的前j个字符所需的最小步数。我们可以从字符串的开头开始逐步计算，逐步填充dp数组。对于每一对字符S[i]和T[j]，我们需要考虑两种情况：如果S[i]等于T[j]，那么我们可以直接将S中的下一个字符移动到T中的下一个位置，此时需要的步数为dp[i-1][j-1]；如果S[i]不等于T[j]，我们需要考虑将S中的某个字符移动到T中的这个位置，此时需要的步数为dp[i-k][j]（其中k为字符串中S到T的最长公共前缀长度）。因此，我们可以通过动态规划的方式计算出最少步数。最终答案即为dp[S的长度][T的长度]。}
创作类型：
原创
本文链接：4.字母游戏一个简单的字母游戏是这样进行的：游戏开始时，我们有两个由小写英文字母组成的串 S 和 T
版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！
分享考题 
