题解 | #牛群编号变更#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param word1 string字符串 
     * @param word2 string字符串 
     * @return int整型
     */
    public int minDistance (String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] f = new int[n + 1][m + 1];

        // 初始化第一行和第一列
        for (int i = 0; i <= n; ++i) {
            f[i][0] = i;
        }
        for (int j = 0; j <= m; ++j) {
            f[0][j] = j;
        }

        // 动态规划计算最小操作次数
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + 1;
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                }
            }
        }

        return f[n][m];
    }
}

本题知识点分析：

1.动态规划

2.数学模拟

3.数组遍历

本题解题思路分析：

1.确定dp数组是什么？以及下标含义，dp数组为每一次两个字符串变成相同所小的次数

2.dp数组递推公式，因为题目中要求的是求最少变化次数,那么运用Math.min进行比较，选出要么是从右边走的，要么是从上边的中变化小的那个。 f[i][j] = Math.min(f[i][j - 1], f[i - 1][j]) + 1;

3.如果字符相同，那么是不需要加1的

  if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
            f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
 }

4.dp数组初始化，第一行和第一列不用变化就可以到达，因为字符串都为空，因此都设置为0

5.确定遍历顺序，是从dp[1][1]开始，其实和向右走和向下走是一样的。

本题使用编程语言: Java

如果您觉得本篇文章对您有帮助的话，可以点个赞支持一下，感谢~