bright

a = input()
b = input()

la, lb = len(a), len(b)

dp = [ [0]*(lb+1) for _ in range(la+1) ] 
lcs = [ ['']*(lb+1) for _ in range(la+1) ] 

for i in range(1,la+1):
  for j in range(1,lb+1):
    if a[i-1] == b[j-1] :
      dp[i][j] = 1+ dp[i-1][j-1]
      lcs[i][j] = lcs[i-1][j-1] + b[j-1] 
    else :
      if dp[i-1][j] > dp[i][j-1] : n,m = i-1, j 
      else : n, m = i, j-1 

      dp[i][j] = dp[n][m]
      lcs[i][j] = lcs[n][m]

print(dp[i][j])
print(lcs[i][j])

print(dp[i][j])
print(lcs[i][j])

a = input()
b = input() 

la = len(a)
lb = len(b)

dp = [ [0]*(lb+1) for _ in range(la+1) ]

for i in range(1,la+1):
  for j in range(1,lb+1):
    if a[i-1] == b[j-1] :
      dp[i][j] = 1+ dp[i-1][j-1] 
    else: 
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  
  # print(dp[i])

print( dp[la][lb] )

www.acmicpc.net/problem/9251

# DP 에서 자주 나오는 내용이므로 잘 이해해보자.  

DP 시간 복잡도   : O(mn)

완전 탐색 복잡도 : O(2^n)

입력 문자열 1 : n 

입력 문자열 2 : m 

step1 )  (n+1)*(m+1) 크기의 dp 배열을 만든다. 

step2 )  규칙 적용하기 

> 규칙 1 :  n[i] == m[i]  -> dp[i][j] = 1 + dp[i-1][j-1]  

               만약 양쪽 문자열 끝의 값이 같다면, 그 두 문자열을 제외한 앞 부분의 최대 길이에 1 을 더한다. 

> 규칙 2 :  n[i] != m[i]  -> dp[i][j] = max( dp[i-1][j] , dp[i][j-1] ) 

               만약 양쪽 문자열 끝의 값이 다르면, 각 문자열이 오기 전 단계의 최대 값을 유지한다. 

step3 ) 이해하기 

n = ABCDE

m = BXDE

   0  B  X  D  E  

0  0  0  0  0  0 

A  0  0  0  0  0     <- A와 BXDF 는 일치하는 값이 없다. 

B  0  1   1  1  1     <- AB와 B / BX / BXD / BXDE 를 비교한다고 생각하면 된다. 

C  0  1   1  1  1 

D  0  1   1  2  2  

E   0  1   1  2  3  

n,m = map(int,input().split()) # n : 열 m : 행

candy = []
for i in range(n):
  candy.append(list(map(int,input().split())))

dp = [ [0]*m for i in range(n) ]

for i in range(n):
  for j in range(m):

    a = i -1
    b = j -1

    tmp = [0] 

    if a >= 0 : 
      tmp.append( dp[a][j] )
    if b >=0 :
      tmp.append( dp[i][b] )
    if a >= 0 and b >=0 : 
      tmp.append( dp[a][b] )
    
    dp[i][j] = candy[i][j] + max(tmp)

print(dp[n-1][m-1])

dp 에 각 칸에서 가질 수 있는 최대 사탕의 수를 입력한다. 

문제에서 움직일 수 있는 경로가 3개 밖에 없으므로 간단하게 구현할 수 있다. 

점화식 : 현재 칸에서의 사탕의 최대 수 :  ( 이동 전 칸이 될 수 있는 곳들 중 사탕의 최대 수 ) + 현재 칸의 사탕 수 

k = int(input())  # 1<= k <= 45 

# A-> B  B -> BA 
a ,b = [0]*(k+1), [0]*(k+1) 
a[0], b[0] = 1,0 

for i in range(1,k+1):
  if i == 1 : 
    a[1] = 0
    b[1] = 1 
    continue 

  a[i] = b[i-1]
  b[i] = a[i-1] + b[i-1]

print (a[k],b[k])​

# 다이나믹으로 풀면... 

k = int(input())  # 1<= k <= 45 

# A-> B  B -> BA 
a ,b = 1, 0 

for i in range(k):
  if i == 0 : 
    a = 0
    b = 1 
    continue 

  tmp = a 
  a = b 
  b = tmp + b 

print (a,b)

# 왜 다이나믹..? 

# 시간 초과  ( 완전 탐색 ) 

n , m= map(int, input().split())

data=[]
for i in range(n):
  data.append( list(map(int,input().split())) )

xy = []
for i in range(m):
  xy.append(list(map(int,input().split())))

def cal( xy ):
  
  s = 0 
  for i in range(xy[0]-1,xy[2]):
    for j in range(xy[1]-1,xy[3]):
      s += data[i][j]

  print (s)

for i in range(m):
  cal(xy[i])
  

# 정답 ( 다이나믹 )