Go: package main

import (
	. "fmt"
    "math"
)

// func init() { Println("----------------------------------------") }

func main() {
    const L_MAX = 1003

	var q int
	Scanf("%d", &q)
	X := make([]string, 0, 150)
	Y := make([]string, 0, 150)
	for i := 0; i < 2 * q; i++ {
	    var tmp string
	    Scanf("%s", &tmp)

	    if i % 2 == 0 {
	        X = append(X, tmp)
	    } else {
	        Y = append(Y, tmp)
	    }
	}

    for i := 0; i < q; i++ {
        dp := make([][]int, L_MAX)
        for k, _ := range dp {
            dp[k] = make([]int, L_MAX)
        }

        x, y := X[i], Y[i]

        // init
        isXFound := false
        for c := 0; c < len(x); c++ {
            if isXFound || y[0] == x[c] {
                dp[0][c] = 1
                isXFound = true
            }
        }
        isYFound := false
        for r := 0; r < len(y); r++ {
            if isYFound || x[0] == y[r] {
                dp[r][0] = 1
                isYFound = true
            }
        }

        for r := 1; r < len(y); r++ {
            for c := 1; c < len(x); c++ {
                // dp[r][c]
                if x[c] == y[r] {
                    dp[r][c] = int(math.Max(float64(dp[r - 1][c - 1] + 1), float64(dp[r][c])))
                }

                dp[r][c] = int(math.Max(float64(dp[r][c]), math.Max(float64(dp[r - 1][c]), float64(dp[r][c - 1]))))
            }
        }
        Println(dp[len(y) - 1][len(x) - 1])

        // LCSも求めておく
        // ans := ""
        // r, c := len(y) - 1, len(x) - 1
        // for r >= 0 && c >= 0 {
        //     if y[r] == x[c] {
        //         ans = string(x[c]) + ans
        //         r--
        //         c--
        //     } else {
        //         if dp[r - 1][c] > dp[r][c - 1] {
        //             r--
        //         } else {
        //             c--
        //         }
        //     }
        // }
        // Println(ans)
    }
}

C++: #include <iostream>
#include <cmath>
#include <string>

using namespace std;

int main(int argc, char const* argv[])
{
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
			string a, b;
			cin >> a;
			cin >> b;
			int **dp = new int*[a.size() + 1];
			for(int j = 0; j < a.size() + 1; j++){
					dp[j] = new int[b.size() + 1];
			}
			for(int j = 0; j <= a.size(); j++)dp[j][0] = 0;
			for(int j = 0; j <= b.size(); j++)dp[0][j] = 0;
			for(int j = 0; j < a.size(); j++){
					for(int k = 0; k < b.size(); k++){
							if(a[j] == b[k])dp[j + 1][k + 1] = dp[j][k] + 1;
							else{
									dp[j + 1][k + 1] = max(dp[j][k], dp[j+1][k]);
									dp[j + 1][k + 1] = max(dp[j + 1][k + 1], dp[j][k+1]);
							}
					}
			}
			cout << dp[a.size()][b.size()] << endl;
	}
	return 0;
}

C++: #include<bits/stdc++.h>
#include<limits.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define MAX 1001

vector<vector<int>> init_c(MAX, vector<int>(MAX, -1));
vector<vector<int>> c(MAX, vector<int>(MAX, -1));
string a, b;

int lcs(int i, int j){
    if(i == 0 || j == 0){
        c.at(i).at(j) = 0;

    }else if(c.at(i).at(j) != -1){
        return c.at(i).at(j);

    }else if(a.at(i - 1) == b.at(j - 1)){
        c.at(i).at(j) = lcs(i-1, j-1) + 1;

    }else{
        c.at(i).at(j) = max(lcs(i, j - 1), lcs(i - 1, j));
    }
    // cout << i << " " << j << " " << c.at(i).at(j) << endl;
    
    return c.at(i).at(j);
}

int main(){
    int q; cin >> q;
    rep(i, q){
        c = init_c;
        cin >> a; cin >> b;
        cout << lcs(a.size(), b.size()) << endl;
    }

}

C++: #include <bits/stdc++.h>
using namespace std;

string a, b;
int N, M;
vector<vector<int> > dp;

int dfs(int n, int m) {
  if ( n == N || m == M ) return 0;
  if ( dp[n][m] >= 0 ) return dp[n][m];
  
  int ret = 0;
  //cout << n << " " << m << " " << cnt << endl;
  if ( a[n] == b[m] ) ret = dfs(n+1, m+1)+1;
  else ret = max(ret, max(dfs(n+1, m), dfs(n, m+1)));

  return dp[n][m] = ret;
}

int main() {
  int q;
  cin >> q;

  while ( q-- ) {
    cin >> a >> b;
    N = a.size();
    M = b.size();
    dp = vector<vector<int> >(N+1, vector<int>(M+1, -1));    
    cout << dfs(0, 0) << endl;
  }
  
  return 0;
}

C++: #include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int q;
    cin >> q;
    vector<int> res(q);

    rep(_, q){
        string x, y;
        cin >> x >> y;
        if(y.size() > x.size()) swap(x, y);

        int n = y.size();
        int m = x.size();

        vector<vector<int>> dp(n, vector<int>(m, 0));
        if(x[0] == y[0]) dp[0][0] = 1;
        else dp[0][0] = 0;

        rep1(i, m){
            if(y[0] == x[i]) dp[0][i] = 1;
            else dp[0][i] = dp[0][i-1];
        }

        rep1(i, n){
            dp[i][0] = dp[i-1][0];
            if(y[i] == x[0]) dp[i][0] = 1;

            rep1(j, m){
                if(y[i] == x[j]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }

        // rep(i, n){
        //     rep(j, m) cout << dp[i][j] << " ";
        //     cout << endl;
        // }

        cout << dp[n-1][m-1] << endl;
        
    }

    return 0;
}

C++: #include <bits/stdc++.h>
#include <cmath>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
//typedef long long ll;
typedef long long ll;
//typedef pair<int, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e15;
const ll MINF = -10e10;
//const int INF = INT_MAX / 100;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)


//ifstream myfile("~/Downloads/02.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

//typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
const double PI = 3.14159265358979323846;

typedef pair<ll, ll> P;


string to_upper(string str) {
    int diff = 'a' - 'A';
    for (int i = 0; i < str.size(); i++) {
        char c = str[i];
        if ('A' <= c && c <= 'Z') {
            c += diff;
            str[i] = c;
        }
    }
    return str;
}


int main() {

    int n;
    cin >> n;

    rep(k, n) {

        string s1, s2;
        cin >> s1 >> s2;
        vector<vector<pair<int, pair<int, int> > > > dp(s1.size() + 1,
                                                        vector<pair<int, pair<int, int> > >(s2.size() + 1));
        for (int i = 0; i <= s1.size(); i++) {
            for (int j = 0; j <= s2.size(); j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = make_pair(0, make_pair(-1, -1));
                } else {
                    dp[i][j] = dp[i][j - 1];
                    if (dp[i][j].first < dp[i - 1][j].first) {
                        dp[i][j] = dp[i - 1][j];
                    }
                    if (s1[i - 1] == s2[j - 1] && dp[i][j].first < dp[i - 1][j - 1].first + 1) {
                        dp[i][j] = make_pair(dp[i - 1][j - 1].first + 1, make_pair(i - 1, j - 1));
                    }
                }
            }
        }
        vector<char> subseq_stack;
        for (int i = s1.size(), j = s2.size(); i > 0 && j > 0;) {
            pair<int, int> next = dp[i][j].second;
            //make_pair(i,j) = next;
            i = next.first;
            j = next.second;
            if (i < 0 || j < 0) break;
            subseq_stack.push_back(s1[i]); // s1[i] == s2[j]
        }
        cout << subseq_stack.size() << endl;
    }
}