台中女中程式解題系統：b033: 兩隻猴子

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b033。
此題用 Dynamic Programming ，可參考 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS  。

演算法(底下文字是從https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS 節錄出來)

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

程式碼：

1. #include <iostream>  
2. #include <cstring>  
3. #include <vector>  
4.   
5. using namespace std;  
6.   
7. int lengthOfLCS(string x, int m, string y, int n) {  
8.     int C[m+1][n+1];  
9.   
10.     for(int i = 0; i <= m; i++)  
11.     {  
12.         for(int j = 0; j <= n; j++)  
13.         {  
14.             if(i == 0 || j == 0)  
15.                 C[i][j] = 0;  
16.             else if(x[i-1] == y[j-1])  
17.                 C[i][j] = C[i-1][j-1] + 1;  
18.             else  
19.                 C[i][j] = max(C[i][j-1], C[i-1][j]);  
20.         }  
21.     }  
22.   
23.     return C[m][n];  
24. }  
25.   
26. int main()  
27. {  
28.     string a, b;  
29.     cin >> a >> b;  
30.   
31.     cout << lengthOfLCS(a, a.length(), b, b.length());  
32.     return 0;  
33. }