SWEA 3044. 최장 공통 부분 수열(Python)

LCS(Longest Common Subsequence)문제이다.
두 문자(ACAYKP, CAPCAK) 을 S1, S2로 정의하고
dp[i][j]를 S1의 i번째와 S2의 j번째 문자위치에서 최대 LCS로 정의한다.

S1의 i번째 문자와 j번째 문자가 같다면,dp[i-1][j-1]에 +1,
S1의 i번재 문자와 j번째 문자가 다르다면 dp[i][j-1]와 dp[i-1][j]중 최대값 (기존의 문자열로 만들수 있었던 최대길이)

• i=0, j=0
  A, C --> LCS의 길이는 0

• i=0, j=1
  A, CA --> LCS의 길이는 1

• i=0, j=2
  A, CAP --> LCS의 길이는 1

• i=0, j=3
  A, CAPC --> LCS의 길이는 1

• i=0, j=4
  A, CAPCA --> LCS의 길이는 1

• i=0, j=4
  A, CAPCAK --> LCS의 길이는 1

• i=1, j=0
  AC, C --> LCS의 길이는 1

• i=1, j=1
  AC, CA --> LCS의 길이는 1

• i=1, j=2
  AC, CAP --> LCS의 길이는 1

• i=1, j=3
  AC, CAPC --> LCS의 길이는 1
  .
  .
  .

res=[]
for m in range(int(input())):
    tmp=""
    S1,S2=map(str,input().split())
    dp=[[0]*(len(S1)+1) for i in range(len(S2)+1)]

    for i in range(1,len(S2)+1):
        for j in range(1,len(S1)+1):
            if S1[j-1]==S2[i-1]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    tmp=dp[-1][-1]
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))