动态规划

题型和提示都很明显的指向动态规划算法，难点在于动态转移方程。

1、状态定义

定义一个二维数组：[i][j]，表示的含义是字符串A的前i个字符，与字符串B的前j个字符的最短编辑距离。

 //状态定义
int[][] f = new int[a.length()+1][b.length()+1];

2、初始化

当字符串A或字符串B为空的时候，那么两字符串之间的编辑距离就是另一个字符串的长度，例如F[0][2] = 2;

for (int i = 0; i <= a.length(); i++) {
                f[i][0] = i;
            }
            for (int i = 0; i <= b.length(); i++) {
                f[0][i] = i;
            }

3、状态转移(重点*难点)

当两个字符串都有字符时，它是如何变化的？我觉得有时候不能光想，画图或许可以更快的发现规律。

假设列为字符串A：abxdyf，行为字符串B：abcdef，按从左到右，从上到下填写下表，观察需要填写的单元格与其左边和上边的值有什么关系？（因为填写是从左到右，从上到下，所以这些值都被提前算出来了，现在就是拿已知推未知）

情况一：

字符串A的第i个字符与字符串B的第j个字符相等，很明显编辑距离就是把想到的这两个字符拿掉，结果等于左上角那个。即：

F[i][j] = f[i-1][j-1];

情况二：

如果F[i][j]中A的第i个字符与字符串B的第j个字符不相等，那么怎么计算？

硬核方法：如果不考虑题意，可以直接看F[i][j]这个格子上边、左边和对角单元格的值去推测转移方程，发现是其上边、左边、左上角的值中最小的+1，然后结合题意去分析验证，因为一般动态规划的规律就是这样。

结合题意去分析，有三种操作：替换、删除、插入。其实在一个字符串插入一个字符，效果等同于在另一个字符串删除一个字符。所以就考虑两种操作：【替换】、【删除】。

（1）替换：

F[i][j]的最后一个字符做一个替换，操作了1次，那剩下就是对字符串A的前i-1个字符和字符串B的前j-1个字符进行编辑操作，而 f[i-1][j-1]的编辑距离我们是知道的，所以就可以求出：F[i][j] = 1+F[i-1][j-1]；

（2）删除：

假设我把字符串A的最后一个字符删除了，操作了1次，那剩下需要计算的就是字符串A的前i-1个字符和字符串B的前j个字符进行编辑，所以：F[i][j] = 1+F[i-1][j]。

然后需要注意的是我也可以删除B的最后一个字符（等同于在A插入的一个字符），然后剩下的编辑距离就是 1+F[i-1][j]。

总结：

情况一是：F[i][j] = f[i-1][j-1];

情况二是：F[i][j] =Min( 1+F[i-1][j-1], 1+F[i-1][j], 1+F[i-1][j])

for (int i = 1; i <= a.length(); i++) {
                for (int j = 1; j <= b.length(); j++) {
                    if (s1.charAt(i-1) == s2.charAt(j-1)){
                        f[i][j] = f[i-1][j-1];
                    }else {
                        f[i][j] = Math.min(Math.min(f[i-1][j-1],f[i-1][j]),f[i][j-1]) + 1;
                    }
                }
            }