字符串相似度（动态规划）

# 问题描述给定一段受损的 DNA 碱基序列 dna1，在每次只操作一个碱基的情况下，将其以最少的操作步骤将其还原到未受损的 DNA 碱基序列 dna2。只可以对 DNA 碱基序列中的一个碱基进行三种操作：
1. 增加一个碱基
2. 去除一个碱基
3. 替换一个碱基## 输入描述:输入两段 DNA 碱基序列，每段分一行输入第一行为第一段受损的 DNA 碱基序列 dna1第二行为第二段未受损的 DNA 碱基序列 dna2## 输出描述:最小操作步骤数**备注**:0 <= dna1.length, dna2.length <= 500dna1 和 dna2 由大写英文字母 A、G、C、T 组成**示例 1****输入**AGCTTAGCAGCTAGCT**输出**2**说明**AGCTTAGC -> AGCTAGC（删除 T）AGCTAGC -> AGCTAGCT（增加 T）**示例 2****输入**AGCCGAGCGCTAGCT**输出**4**说明**AGCCGAGC -> GCCGAGC（删除 A）GCCGAGC -> GCTGAGC（将 C 替换为 T）GCTGAGC -> GCTAGC（删除 G）GCTAGC -> GCTAGCT（增加 T）

算法分析： 

• 它通过递归比较两个字符串，考虑插入、删除和替换操作来计算需要的最小编辑次数

代码： 

public class Main {public static int correct_len(String dna1, String dna2, int ans) {if (dna1 == "") {return ans + dna2.length();} else if (dna2 == "") {return ans + dna1.length();} else if (dna1.charAt(0) == dna2.charAt(0)) {return correct_len(dna1.substring(1), dna2.substring(1), ans);}return Math.min(correct_len(dna2.charAt(0) + dna1, dna2, ans + 1), Math.min(correct_len(dna1.substring(1), dna2, ans + 1),correct_len(dna1.substring(1), dna2.substring(1), ans + 1)));}public static int solution(String dna1, String dna2) {return correct_len(dna1, dna2, 0);}public static void main(String[] args) {// You can add more test cases hereSystem.out.println(solution("AGCTTAGC", "AGCTAGCT") == 2);System.out.println(solution("AGCCGAGC", "GCTAGCT") == 4);}
}