题解 | #牛群编号变更# Java

`编辑距离`原题简化版 这题还可以是 `插入`、`删除`、`修改`三个操作，还可以把每个操作赋予一个代价，求最少操作代价

dp[i][j]表示将字符串word1的前i个字符变为字符串word2的前j个字符所需的最少操作次数。

我们需要初始化dp数组的边界条件。当word1为空串时，也就是i=0时，dp[0][j]等于j，表示将空串变为word2的前j个字符需要插入j个字符。同理，当word2为空串时，也就是j=0时，dp[i][0]等于i，表示将word1的前i个字符变为空串需要删除i个字符。

通过递推关系式来更新dp数组的其他位置。对于dp[i][j]，如果word1的第i个字符等于word2的第j个字符，说明不需要进行操作，此时可以继续判断dp[i-1][j-1]，即dp[i][j] = dp[i-1][j-1]。如果word1的第i个字符不等于word2的第j个字符，说明需要进行操作，然后可以选择插入字符、删除字符中的一种操作，即dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);

import java.util.*;


public class Solution {

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        int[][] dp = new int[m + 1][n + 1];

        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++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1);
                }
            }
        }

        return dp[m][n];
    }
}