知識點：動態(tài)規(guī)劃

思路：

這段代碼實現(xiàn)了求解兩個字符串的最小編輯距離。采用動態(tài)規(guī)劃的思想，通過構(gòu)建一個二維數(shù)組?f?作為動態(tài)規(guī)劃表。表中的每個元素?f[i][j]?表示將?word1?的前?i?個字符轉(zhuǎn)換成?word2?的前?j?個字符所需的最小編輯距離。

首先，初始化動態(tài)規(guī)劃表的邊界條件。?f[i][0]?表示將?word1?的前?i?個字符轉(zhuǎn)換成空字符串所需的編輯距離，即?i；f[0][j]?表示將空字符串轉(zhuǎn)換成?word2?的前?j?個字符所需的編輯距離，即?j。

然后，通過迭代計算動態(tài)規(guī)劃表中的其他元素。對于每個?f[i][j]，有兩種情況：

1. 如果?word1?的第?i?個字符和?word2?的第?j?個字符相等，那么在編輯的過程中不需要進行任何操作，此時?f[i][j] = f[i-1][j-1]。
2. 如果?word1?的第?i?個字符和?word2?的第?j?個字符不相等，那么可以進行三種操作：刪除?word1?的第?i?個字符，插入?word2?的第?j?個字符，或者將?word1?的第?i?個字符替換為?word2?的第?j?個字符。因此?f[i][j]?可以由下面三者中的最小值得出：f[i-1][j]?+ 1：表示刪除?word1?的第?i?個字符。f[i][j-1]?+ 1：表示插入?word2?的第?j?個字符。f[i-1][j-1]?+ 1：表示將?word1?的第?i?個字符替換為?word2?的第?j?個字符。

最后，返回?f[n][m]，即將?word1?轉(zhuǎn)換成?word2?的最小編輯距離。

編程語言：java

import java.util.*;


public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     *
     * @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 - 1][j], f[i][j - 1]) + 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];
    }
}