原文出处：https://algorithms.tutorialhorizon.com/dynamic-programming-edit-distance-problem/
问题：假设我们现在有两个字符串s1和s2，并且给出如下所示的三个编辑操作，写出一个算法，当每次只能使用其中一个编辑操作时，找到将字符串s1转换成s2的最小编辑次数。
允许的编辑操作：
1.insert-插入一个字符
2.delete-删除一个字符
3.replace-将字符串中的一个字符用另一个字符代替
例如：
String s1 = "horizon" String s2 = "horzon" Output: 1 {remove 'i' from string s1} String s1 = "horizon" String s2 = "horizontal" Output: 3 {insert 't', 'a', 'l' characters in string s1}
分析：从后往前依次比较字符串中的每一个字符，对于每次比较之后的结果，我们执行如下两种操作将问题变成子问题：
1.如果两个字符串末尾的字符相等，那么我们忽视最后一个字符，将问题转化为找到剩下的字符组成的字符串的编辑距离
2.如果两个字符串末尾的字符不相等，那么我们分别执行以上三种操作（insert，delete，replace），执行完之后，再递归的
解决两个字符串的编辑距离。
算法：假设我们有长度为n的字符串s1和长度为m的字符串s2，比较s1和s2末尾的字符：
1.如果两个字符相等，那么忽视末尾字符，求前n-1和m-1的字符串的编辑距离
2.如果两个字符不相等，那么执行如下三种操作，并且选择其中的最优解：
a.在s1的末尾插入一个字符，该字符和s2末尾的字符相同，此时s1的长度是n+1,s2的长度是m。然后忽视末尾字符，求前n和前m-1的字符串的编辑距离x1
b.将s1的末尾的字符删掉，此时s1的长度是n-1，s2的长度是m。求长度为n-1和m的字符串的编辑距离x2
c.将s1的末尾的字符用s2的末尾的字符代替，然后求前n-1和m-1的编辑距离x3
编辑距离就是x1+1, x2+1, x3+1中的最小值
同时，我们可以用动态规划自底向上来降低时间复杂度