[알고리즘] dp

다이나믹 프로그래밍의 조건
1. 최적 부분 구조(Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제(Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 한다.

점화식: 인접한 항들 사이의 관계식 만들기

 

피보나치 수열 탑다운 프로그래밍

d = [0]*100 #메모이제이션 하기 위한 리스트 초기화
def fibo(x):
  if x==1 or x==2: #종료조건
    return 1
  if d[x]!=0: #이미 계산한 적이 있다면 그대로 반환
    return d[x]
  d[x]=fibo(x-1)+fibo(x-2) #아직 계산하지 않았다면 점화식에 따라서 결과 반환
  return d[x]

print(fibo(99))

피보나치 수열 바텀업 프로그래밍

d = [0]*100 #메모이제이션 하기 위한 리스트 초기화
d[1]=1
d[2]=1
n=99
for i in range(3,n+1):
  d[i]=d[i-1]+d[i-2] #점화식
print(d[n])

금광

for tc in range(int(input())):
  n,m = map(int,input().split())
  array = list(map(int,input().split()))
  dp=[]
  for i in range(n):
    dp.append(array[i*m:(i+1)*m])

  for j in range(1,m):
    for i in range(n):
      #왼쪽 위에서 오는 경우
      if i==0: left_up=0
      else: left_up=dp[i-1][j-1]
      #왼쪽 아래에서 오는 경우
      if i==n-1: left_down=0
      else: left_down=dp[i+1][j-1]
      #왼쪽에서 오는 경우
      left=dp[i][j-1]
      dp[i][j] = dp[i][j]+max(left_down,left,left_up)
  result=0
  for i in range(n):
    result = max(result,dp[i][m-1])
  print(result)

 

 

LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분수열) 알고리즘(문제 : 병사 배치하기)

점화식 : 모든 0<=j<i에 대하여, D[i]=max(D[i],D[j]+1) if array[j]<array[i]

n= int(input())
arr = list(map(int,input().split()))
arr.reverse()
dp=[1]*n
for i in range(1,n):
  for j in range(0,i):
    if arr[j]<arr[i]:
      dp[i]=max(dp[i],dp[j]+1)
print(n-max(dp))