动态规划 10

原题链接

动态规划

二维dp，x轴为word1，y轴为word2，dp[i][j] 的含义表示word1从0到i 的一段，转化为，word2从0到j 的一段需要的步骤。

从word1 的 0 下标和 word2 的 0 下标开始，即两个空字符串开始，依次递增下标。

1、如果当前字符相等，word1.charAt(i - 1) == word2.charAt(j - 1)，则不需要操作，直接dp[i][j] = dp[i-1][j-1]

2、如果当前字符不相等，则有三种操作可以执行。在这三种操作中取得最小值 并 加1(加上当前操作)。

• 替换 ：dp[i][j] = dp[i-1][j-1] + 1
• 增加 ：dp[i][j] = dp[i][j-1] + 1
• 删除 ：dp[i][j] = dp[i-1][j] + 1

Note：以上操作是针对word1的操作，所以操作完之后，无论是i-1还是j-1还是i、j同时-1，在操作完之后，他们都需要+1，即为当前操作数，使得word1 == word2。

所以递推方程为：

if(word1[i - 1] == word[j - 1]) dp[i][j] = dp[i-1][j-1]

else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;

初始化：先看 i == 0的情况，相当于word1一直为空字符串，word2递增，所以word1要转换成word2需要增加字符，随着word2的增加而增加，dp[0][j] = j; (j = 0; j <= n2)

接着是 j == 0的情况，相当于word1递增，word2一直为空字符串，所以word1要转换成word2需要减少字符，随着word1的增加而增加，dp[i][0] = i; (i = 0; i <= n1)

int n1 = word1.length();
int n2 = word2.length();

代码如下

public class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n2; j++) {
            dp[0][j] = j;
        }
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        for (int i = 0; i <= n1; i++) {
            for (int j = 0; j <= n2; j++) {
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }
        return dp[n1][n2];
    }

    public static void main(String[] args) {
        String s1 = "horse";
        String s2 = "ros";
        System.out.println(new Solution().minDistance(s1, s2));
    }
}