Go: package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}

Python: # -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
# 4/5??§Time Limit Exceeded 5.20s ????????????5s??\???????????????????????????

# c = []  # global?????????????????????????
def prep_array(X, Y):
    """ ??????0???2?¬???????????????¨??????????????????????????\????????????????????§??????????????????????¨?(1000+1)??\???????????? """
    from array import array
    c = [[0]*1024 for _ in range(1024)]
    # c = [array('I', [0] * 1024) for _ in range(1024)]
    return c


def check_max(array):
    """ 2?¬????????????????????????§??????????????? """
    max_lcs = 0
    for row in array:
        temp_max = max(row)
        if temp_max > max_lcs:
            max_lcs = temp_max
    return max_lcs


def calc_lcs4(X, Y, c):
    """
    Y[j]?????¢???????????????????????´
    ???????????????????????°???????????????????????´
    4/5 ?????????????????????????????¨????????????????????????????????°??§6.0?§?
    """
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0

    pre_row = c[0]
    for i in range(1, m):
        row = c[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                cv = pr_j1 + 1
                row[j] = cv
                if cv > max_lcs:
                    max_lcs = cv
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j]= pr_j
                else:
                    row[j] = r_j1
        pre_row = row
    return max_lcs



def calc_lcs3(X, Y, c):
    """
    X[i]???for j?????????????????????????????°????????????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§7.1?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        XX = X[i]
        for j in range(1, n+1):
            if XX == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)



def calc_lcs2(X, Y, c):
    """
    c[i][j]????????¢????????????????????????????????§?????????????????¨?????????????????°??????????????????????????£??????????????§???
    4/5 ?????????????????????????????¨????????????????????????????????°??§8.2?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    pre_row = c[0]
    for i in range(1, m+1):
        row = c[i]
        for j in range(1, n+1):
            if X[i] == Y[j]:
                row[j] = pre_row[j - 1] + 1
            elif pre_row[j] >= row[j - 1]:
                row[j] = pre_row[j]
            else:
                row[j] = row[j - 1]
        pre_row = row
    return check_max(c)


def calc_lcs1(X, Y):
    """
    array?????????????????¨???byte???????????¨????????¨????§??????????????????????????????????????????§?????¨???????????£?????????int???????????¨???
    4/5 ?????????????????????????????¨????????????????????????????????°??§19.3?§?
    """
    from array import array
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y
    c = array('i', [0] * (1024 * 1024))
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i*1024 + j] = c[(i-1)*1024 + j - 1] + 1
            elif c[(i-1)*1024 + j] >= c[i*1024 + j - 1]:
                c[i*1024 + j] = c[(i-1)*1024 + j]
            else:
                c[i*1024 + j] = c[i*1024 + j - 1]
    return max(c)


def calc_lcs1_1(X, Y):
    """

    4/5 ?????????????????????????????¨????????????????????????????????°??§7.1?§?
    """
    from array import array
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)
    max_lcs = 0
    C = [array('I', [0] * n) for _ in range(m)]

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y[1:]):
            if XX == YY:
                pr_j1 = pre_row[j-1]
                row[j] = pr_j1 + 1
                if row[j] > max_lcs:
                    max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j]= r_j1
        pre_row = row
    return max_lcs


def calc_lcs(X, Y, c):
    """
    ??????????????¢?????´????????????????????????????£?????????????
    4/5 ?????????????????????????????¨????????????????????????????????°??§12.5?§?
    """
    m = len(X)
    n = len(Y)
    X = ' ' + X
    Y = ' ' + Y

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i] == Y[j]:
                c[i][j] = c[i - 1][j - 1] + 1
            elif c[i - 1][j] >= c[i][j - 1]:
                c[i][j] = c[i - 1][j]
            else:
                c[i][j] = c[i][j - 1]
    return check_max(c)


if __name__ == '__main__':
    # ??????????????\???
    num = int(input())
    # f = open('input.txt')
    # num = int(f.readline())

    for _ in range(num):
        X = input()
        Y = input()
        # X = f.readline().strip()
        # Y = f.readline().strip()

        # ???????????????
        result = calc_lcs4(X, Y, prep_array(X, Y))
        # result = calc_lcs1_1(X, Y)

        # ???????????¨???
        print(result)

Python: q = int(input())
for i in range(q):
    X = input()
    Y = input()

    m, n = len(X), len(Y)
    c = [[0 for i in range(n+1)] for j in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            x, y = X[i-1], Y[j-1]
            if x == y:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = max(c[i-1][j], c[i][j-1])

    print(c[m][n])

Python: 
def main():
    Q = int(input())
    XY = []
    for i in range(Q):
        X = input()
        Y = input()
        XY.append((X,Y))
    for X,Y in XY:
        
        LX,LY = len(X), len(Y)
        dp = [0 for _ in range(LY+1)]

        for i in range(LX):
            ex = dp[:]
            for j in range(LY):
                if X[i] == Y[j]:
                    dp[j+1] = ex[j] + 1
                elif dp[j+1] < dp[j]:
                    dp[j+1] = dp[j]
        print(dp[-1])


if __name__ == "__main__":
    main()

Python: n=int(input())

for i in range(n):
    a=list(input())
    b=list(input())
    x=len(a)+1
    y=len(b)+1

    r=[[0 for j in range(y)]for i in range(x)]

    for j in range(1,x):
        for k in range(1,y):
            c=max(r[j-1][k-1],r[j-1][k],r[j][k-1])
            if a[j-1]==b[k-1]:
                c=max(r[j-1][k-1]+1,r[j-1][k],r[j][k-1])
            
            r[j][k]=c    
    print(r[x-1][y-1])