LeetCode ---- 72. 編輯距離 （java）

求最值，動态規劃題。

用 

dp[i][j]

 表示從 

word[0...i]

 轉換到 

word[0...j]

 的最小操作，使用動态規劃求解

class Solution {
    public int minDistance(String word1, String word2) {
       
        int row = word1.length();
        int col = word2.length();
        
         //dp[i][j]表示word1[0...i]變為word2[0...j]所使用的最少操作數
        int[][] dp = new int[row+1][col+1];
        
        //初始化:當word1為空字元串“”時，row=0
        for(int j = 0; j <= col; j++){
            dp[0][j] = j; //操作為：插入字元
        }
        
         //初始化:當word2為空字元串“”時,col=0
        for(int i = 0; i <= row; i++){
            dp[i][0] = i; //操作為：删除字元
        }
        
        for(int i = 1; i <= row ; i++){
            for(int j = 1; j <= col; j++){
                //末尾字元相同，不需要編輯.(對應字元相等，不操作.)(注意下标，dp[][]下标為從1開始，字元串下标從0開始)
                if(word1.charAt(i-1) == word2.charAt(j-1)){//是以要減去1
                     dp[i][j] = dp[i-1][j-1];
                }else{
                    // 末尾字元不同，三種編輯情況，取最小值
                    //需要操作，對應操作分别為：替換，删除，插入
                     dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                }
               
            }
        }
        
        return dp[row][col];
    }
}
           

題解ref：

https://leetcode-cn.com/problems/edit-distance/solution/zi-di-xiang-shang-he-zi-ding-xiang-xia-by-powcai-3/