题目描述
小蓝拥有两个字符串S,T。他希望通过如下操作使得字符 S 转换为字符串 T。
操作有一下三种：
- 删除一个字符。插入一个字符。将一个字符改为另一个字符。
问最少需要操作多少次才可以使得字符串 S 转换为字符串 T。
输入描述
输入第一行包含一个字符串 S。
输入第二行包含一个字符串 T。
1≤∣S∣,∣T∣≤2×10^3，保证 S、T 只包含小写字母
输出描述
输出一个整数表示答案。
输入输出样例
示例 1
输入
abc aa
输出
2
这题就是明显的动态规划，我们用两个char型数组a[]和b[]来储存输入的两个字符串，数组dp[][]存储的是需要改变的操作次数。
当a[i]==b[j]时，则状态转移方程为dp[i][j]=dp[i-1][j-1]。
当a[i]!=b[j]时，则dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j], dp[i][j-1]))+1;
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j], dp[i][j-1]))+1的意思是在dp[i-1][j-1]
dp[i][j-1],dp[i-1][j]中选出最小的操作数然后加上1，其中dp[i-1][j-1]的意思就是替换，而dp[i][j-1]的意思就是删除，dp[i-1][j]的意思是插入。
import java.util.*;
public class Main{
static int N=3005;
static char[]a=new char[N];
static char[]b=new char[N];
static int [][]dp=new int [N][N];
public static int solve(String s,String t) {
for(int i=1;i<=s.length();i++)
a[i]=s.charAt(i-1); //将输入的字符串转化为数组存储
for(int i=1;i<=t.length();i++)
b[i]=t.charAt(i-1);
for(int i=1;i<=s.length();i++)
dp[i][0]=i;
for(int j=1;j<=t.length();j++)
dp[0][j]=j;
for(int i=1;i<=s.length();i++)
for(int j=1;j<=t.length();j++) {
if(a[i]==b[j])//当两字符相同时
dp[i][j]=dp[i-1][j-1];
else {//当不同时则从替换，删除，插入中找最小数然后加一
dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j], dp[i][j-1]))+1;
}
}
return dp[s.length()][t.length()];
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
String s=in.next();
String t=in.next();
int ans=solve(s,t);
System.out.println(ans);
}
}
