题解 | #编辑距离(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str1 string字符串
     * @param str2 string字符串
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        // write code here
        if (str1 == null || str2 == null) return 0;
        char[] cs1 = str1.toCharArray();
        char[] cs2 = str2.toCharArray();
        int[][] dp = new int[cs1.length + 1][cs2.length + 1];
        dp[0][0] = 0;
        // 第0列,初始化第一个列竖向值次数
        for (int i = 1; i < cs1.length; i++) {
            // cs1[1,i]转为cs2[0,0]的值次数为i值
            dp[i][0]=i;
        }
        // 第0行,初始化第一个横向值次数
        for (int j = 1; j < cs2.length; j++) {
            // cs1[0,0]转为cs2[0,j]的值次数为j值
            dp[0][j]=j;
        }
        // 其他行和列，三种情况，从左到右，从上到下扫描
        for (int i = 1; i < cs1.length; i++) {
            for (int j = 1; j < cs2.length; j++) {
                // 第一种情况从上方下来，对应上方次数+1次数即可
                int top = dp[i-1][j] + 1;
                // 第二种情况从上方下来，对应左方次数+1次数即可
                int left = dp[i][j-1] + 1;
                // 第三种情况从左上角过来，需要判断俩字符值是否相等，不相等左上角次数+1
                int leftTop = dp[i-1][j-1];
                if(cs1[i-1] != cs2[j-1]){
                    leftTop++;
                }
                dp[i][j] = Math.min(Math.min(top,left),leftTop);
            }
        }
        return dp[cs1.length][cs2.length];
    }
}

解题思想：动态规划思想，状态方式+状态转移方程+求最值，已知推未知，局部最优推导总体最优