申論題 - 阿摩線上測驗

申論題資訊

試卷：112年 - 112-1 臺北市立建國高級中學正式教師甄選:資訊科技#114097
科目：教甄◆資訊科技概論專業(電腦科)
年份：112年
排序：0

申論題內容

3. 最長共同子序列（Longest Common Subsequence，LCS）是動態規劃的一個經典應用。這個問題最早起源於 DNA 序列的比對問題：如果有兩段 DNA 序列，它們有多相似呢？現在給定兩個字串 String1 以及 String2，找出它們最長共同子序列的長度程式碼如下所示，請完成...的程式部分。(本題 5 分) 【範例輸入】
Enter String1: ABCDE
Enter String2: BCD
【範例輸出】
3

詳解 (共 1 筆)

詳解提供者：阿茹茹茹

for(int i=1;i<=s1n;i++){

for(int j=1;j<=s2n;j++){

if(s1[i-1]==s2[i-1]){

lcs[i][j]=lcs[i-1][j-1]+1;

}

else{

lcs[i][j]=max(lcs[i][j-1],lcs[i-1][j]);

}