DP问题

题目描述

DP分析

初始化：
如果 dna1 为空，那么将 dna1 转换成 dna2 需要插入 dna2 的所有字符，因此 dp[0][j] = j。
如果 dna2 为空，那么将 dna1 转换成 dna2 需要删除 dna1 的所有字符，因此 dp[i][0] = i。

状态转移：
如果 dna1[i-1] == dna2[j-1]，那么 dp[i][j] = dp[i-1][j-1]，因为不需要任何编辑步骤。
否则，dp[i][j] 可以通过以下三种方式得到：
插入：dp[i][j-1] + 1
删除：dp[i-1][j] + 1
替换：dp[i-1][j-1] + 1
取这三种方式的最小值作为 dp[i][j]。
最终结果：
dp[dna1.length()][dna2.length()] 即为将 dna1 转换成 dna2 所需的最少编辑步骤。

public class Main {
    public static int solution(String dna1, String dna2) {
        int len1 = dna1.length(), len2 = dna2.length();
        int[][] f = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len2; i++) f[0][i] = i;
        for (int i = 0; i <= len1; i++) f[i][0] = i;
        for (int i = 1; i <= len1; i++)
            for (int j = 1; j <= len2; j++)
                if (dna1.charAt(i - 1) == dna2.charAt(j - 1)) f[i][j] = f[i - 1][j - 1];
                else {
                    int t = Math.min(f[i][j - 1], f[i - 1][j]) + 1;
                    t = Math.min(t, f[i - 1][j - 1] + 1);
                    f[i][j] = t;
                }

        return f[len1][len2];
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        System.out.println(solution("AGCTTAGC", "AGCTAGCT") == 2);
        System.out.println(solution("AGCCGAGC", "GCTAGCT") == 4);
    }
}