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：