脫氧核糖核酸即常說的DNA，是一類帶有遺傳信息的生物大分子。它由4種主要的脫氧核苷酸(dAMP、dGMP、dCMT和dTMP)通過磷酸二酯鍵連接而成。這4種核苷酸可以分別記為：A、G、C、T。

    DNA攜帶的遺傳信息可以用形如：AGGTCGACTCCA.... 的串來表示。DNA在轉錄復制的過程中可能會發生隨機的偏差，這才最終造就了生物的多樣性。

    為了簡化問題，我們假設，DNA在復制的時候可能出現的偏差是（理論上，對每個堿基被復制時，都可能出現偏差）：

　　1. 漏掉某個脫氧核苷酸。例如把 AGGT 復制成為：AGT

    2. 錯碼，例如把 AGGT 復制成了：AGCT

    3. 重碼，例如把 AGGT 復制成了：AAGGT

    如果某DNA串a，最少要經過 n 次出錯，才能變為DNA串b，則稱這兩個DNA串的距離為 n。

    例如：AGGTCATATTCC 與 CGGTCATATTC 的距離為 2

    你的任務是：編寫程序，找到兩個DNA串的距離。

【輸入、輸出格式要求】

    用戶先輸入整數n(n<100)，表示接下來有2n行數據。

    接下來輸入的2n行每2行表示一組要比對的DNA。（每行數據長度<10000）

    程序則輸出n行，表示這n組DNA的距離。

    例如：用戶輸入：
3
AGCTAAGGCCTT
AGCTAAGGCCT
AGCTAAGGCCTT
AGGCTAAGGCCTT
AGCTAAGGCCTT
AGCTTAAGGCTT

    則程序應輸出：
1
1
2

結題思路：參閱百度百科http://baike.baidu.com/view/2020247.htm
代碼如下：

import java.util.*;


public class Main {
    
    
    static String instr0;
    static String instr1;
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        for(int ii = 0; ii < N; ii++){
            instr0 = sc.nextLine();
            instr1 = sc.nextLine();
            int rs = pro();
            System.out.println(rs);
        }
        
    }
    static int pro(){
        int[][] dis = new int[instr0.length()][instr1.length()];
        for(int i = 0; i < instr0.length(); i++)
            dis[i][0] = i;
        for(int j = 0; j < instr1.length(); j++)
            dis[0][j] = j;
        for(int i = 1; i < instr0.length(); i++){
            for(int j = 1; j < instr1.length(); j++){
                int cost = 0;
                if(instr0.charAt(i) != instr1.charAt(j))
                    cost = 1;
                dis[i][j] = min3(dis[i - 1][j] + 1, dis[i][j - 1] + 1, 
                        dis[i - 1][j - 1] + cost);
            }
        }
        return dis[instr0.length() - 1][instr1.length() - 1];
        
    }
    static int min3(int a, int b, int c){
        return Math.min(Math.min(a, b), c);
    }

    
}