題目如下：
眾所周知，人類基因可以被認為是由4個核苷酸組成的序列，它們簡單的由四個字母A、C、G和T表示。生物學家一直對識別人類基因和確定其功能感興趣，因為這些可以用于診斷人類疾病和設計新藥物。
生物學家確定新基因序列功能的方法之一是，用新基因作為查詢搜索數據庫，要搜索的數據庫中存儲了基因序列及其功能。數據庫搜索將返回數據庫中與查詢基因相似的基因序列表。
生物學家認為序列相似性往往意味著功能相似性，因此新基因的功能可能是來自列表的基因的功能之一，要確定哪一個是正確的，需要另一系列的生物實驗。請設計一個動態規劃算法比較兩個基因并確定它們的相似性，然后編寫程序實現該算法。
給定兩個基因AGTGATG和GTTAG，它們有多相似？測量兩個基因相似性的一種方法稱為對齊。在對齊中，如果需要，將空間插入基因的適當位置以使它們等長，并根據評分矩陣評分所得基因。
例如，在AGTGATG中插入一個空格得到AGTGAT-G，并且在GTTAG中插入3個空格得到-GT—TAG。空格用減號(-)表示。兩個基因現在的長度相等，這兩個字符串對齊如下：
AGTGAT-G
-GT--TAG
在這種對齊中有4個字符是匹配的，即第2個位置的G，第3個位置的T，第6個位置的T和第8個位置的G。每對對齊的字符根據評分矩陣分配一個分數，不允許空格之間進行匹配。上述對齊的得分為(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。評分矩陣如下：
當然，還有許多其他的對齊方式（將不同數量的空格插入到不同的位置得到不同的對齊方式），例如：
AGTGATG
-GT TA -G
該對齊的得分數是(-3)+5+5+(-2)+5+(-1)=14，這個對齊更好，且是最佳的。因此，這兩個基因的相似性是14。
輸入格式:
輸入由T個測試用例組成，T在第1行輸入，每個測試用例由兩行組成，每行包含一個整數（表示基因的長度）和一個基因序列，每個基因序列的長度至少為1，不超過100。
輸出格式:
打印每個測試用例的相似度，每行一個相似度。
輸入樣例:
在這里給出一組輸入。例如：
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
輸出樣例:
在這里給出相應的輸出。例如：
14
21解題思路如下：
?題目要求計算兩個基因序列的相似性得分，我們可以通過動態規劃方法找到最優的對齊方式。設dp[i][j] 表示序列 gene1[0..i-1] 和 gene2[0..j-1] 的最優對齊得分。設評分矩陣similarityMatrix的行和列分別對應?A, C, G, T, -。利用評分矩陣進行匹配，對比三種情況：gene1[i-1]?和?gene2[j-1]?直接匹配，gene1[i-1]?與空格匹配，gene2[j-1]?與空格匹配，取這三種情況的最大值作為?dp[i][j] 。
具體代碼如下：
import java.util.Scanner;public class Main {private static final int MAX_N = 100;private static final int[][] similarityMatrix = {{ 5, -1, -2, -1, -3 },{ -1, 5, -3, -2, -4 },{ -2, -3, 5, -2, -2 },{ -1, -2, -2, 5, -1 },{ -3, -4, -2, -1, 0 }};private static int iGene(char a) {switch (a) {case 'A': return 0;case 'C': return 1;case 'G': return 2;case 'T': return 3;default: return 4; // Gap character '-'}}private static int calculateSimilarity(String gene1, String gene2, int n1, int n2) {int[][] dp = new int[n1 + 1][n2 + 1];for (int i = 1; i <= n1; i++) {dp[i][0] = dp[i - 1][0] + similarityMatrix[iGene(gene1.charAt(i - 1))][4];}for (int j = 1; j <= n2; j++) {dp[0][j] = dp[0][j - 1] + similarityMatrix[iGene(gene2.charAt(j - 1))][4];}for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {int match = dp[i - 1][j - 1] + similarityMatrix[iGene(gene1.charAt(i - 1))][iGene(gene2.charAt(j - 1))];int delete = dp[i - 1][j] + similarityMatrix[iGene(gene1.charAt(i - 1))][4];int insert = dp[i][j - 1] + similarityMatrix[iGene(gene2.charAt(j - 1))][4];dp[i][j] = Math.max(Math.max(match, delete), insert);}}return dp[n1][n2];}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();while (T-- > 0) {int n1 = scanner.nextInt();String gene1 = scanner.next();int n2 = scanner.nextInt();String gene2 = scanner.next();int similarity = calculateSimilarity(gene1, gene2, n1, n2);System.out.println(similarity);}scanner.close();}
}運行結果如下：
答案正確?
