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

    DNA攜帶的遺傳信息可以用形如：AGGTCGACTCCA.... 的串來(lái)表示。DNA在轉(zhuǎn)錄復(fù)制的過(guò)程中可能會(huì)發(fā)生隨機(jī)的偏差，這才最終造就了生物的多樣性。

    為了簡(jiǎn)化問(wèn)題，我們假設(shè)，DNA在復(fù)制的時(shí)候可能出現(xiàn)的偏差是（理論上，對(duì)每個(gè)堿基被復(fù)制時(shí)，都可能出現(xiàn)偏差）：

　　1. 漏掉某個(gè)脫氧核苷酸。例如把 AGGT 復(fù)制成為：AGT

    2. 錯(cuò)碼，例如把 AGGT 復(fù)制成了：AGCT

    3. 重碼，例如把 AGGT 復(fù)制成了：AAGGT

    如果某DNA串a(chǎn)，最少要經(jīng)過(guò) n 次出錯(cuò)，才能變?yōu)镈NA串b，則稱這兩個(gè)DNA串的距離為 n。

    例如：AGGTCATATTCC 與 CGGTCATATTC 的距離為 2

    你的任務(wù)是：編寫程序，找到兩個(gè)DNA串的距離。

【輸入、輸出格式要求】

    用戶先輸入整數(shù)n(n<100)，表示接下來(lái)有2n行數(shù)據(jù)。

    接下來(lái)輸入的2n行每2行表示一組要比對(duì)的DNA。（每行數(shù)據(jù)長(zhǎng)度<10000）

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

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

    則程序應(yīng)輸出：
1
1
2

結(jié)題思路：參閱百度百科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);
    }

    
}