583. Delete Operation for Two Strings

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

动态规划，创建数组dp[][]，长宽分别为两个字符串的长度。
在dp中填入子字符串修改成另一个子字符串时需要删除的数量。
如果两个字符相同，则相对于上一个状态不需要增加数量。因此可以直接等于对角线方向上的值。
如果两个字符串不同，则取上方向和左方向中的较小值，然后+1。（由于题目只允许删除操作，不允许修改操作，因此不能从字符串左上角取值。）
最后返回dp中右下角的值。

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            char k = bin1[i-1];
            for(int j = 1; j <= n; j++){
                if(k == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}