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