72. Edit Distance
给你两个字串word1和word2，我们可以对字串三种操作，分别是：
* 插入一个字符到word1
* 删除word1的一个字符
* 替换掉word1中的一个字符
我们要找出word1经过上面三种操作后变成word2所需要的最小次数。
Example：
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
思路：
1.字串问题大多数都可以采动态规划处理，首先我们创立一个二维阵列dp[i][j]，
表示长度为 i 的word1 转换为长度为 j 的word2所需的最小操作次数。
2.找出状态转移方程式
我们可以透过下列方式更新矩阵的值：
若s1[i]和s2[j]相同，那么不需要做任何操作，dp[i][j]会等于dp[i-1][j-1]。
若s1[i]和s2[j]不相同，我们比较插入、删除、替换这三种操作哪个做最少次：
插入：若我们要插入一个c到s1，需要一次操作且变为s1[1..i] + c，我们可以透过
dp[i][j-1] + 1来更新。
删除：若我们要从s1删除一个c，需要一次操作且变为s1[1...i-1]，我们可透过
dp[i-1][j] + 1来更新。
替换：若我们要从s1替换掉一个c，需要一次操作且变为s1[1...i-1] + c ，我们可以透
过dp[i-1][j-1] + 1来更新。
3.决定dp初始条件
因为要检查dp[i-1][j-1]为了避免越界我们用两个loop初始化dp[0][j]和dp[i][0]。
4.用双层loop把dp表格填满后返回dp[m][n]
JavaCode：