题解 | #牛群编号变更#

所用语言

Java

所用知识

动态规划

解题思路

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

完整的代码

public int minDistance (String word1, String word2) {
    int m= word1.length();
    int n= word2.length();
    int[][] f = new int[m+1][n+1];
    for(int i=0;i<=m;i++){
        f[i][0] = i;
    }
    for(int j=0;j<=n;j++){
        f[0][j] = j;
    }

    for(int i=1;i<=m ;i++){
        for(int j=1;j<=n;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[m][n];

}