DP

[ssionii]

DP (동적계획법)

수학적 귀납법을 이용한 문제풀이 기법

• 어떤 상태 N과 그 다음 상태 N+1을 정의하는 식을 각각 f(N), f(N+1)이라 하고, f(N+1)이 f(N)으로 부터 유도가 가능하면, 임의의 값 x에 대해서 f(x)의 값도 쉽게 구할 수 있다. 이때 f(x+1) = af(x)+b와 같은 식을 점화식이라고 한다. (DP 문제 == 점화식을 세울 수 있는 문제)

• 주의 할 점 - memoization
  두 번 이상 계산하지 않기 위해 처음 정답을 구했을 때 메모리에 기록
  알고리즘을 반복문 형태로 구현하면 memoization 기법이 필요 없지만, 재귀형태로 DP 문제를 푼다면 반드시 memoization 기법을 사용해야한다.

1. base case
2. memo 한거 활용
3. 계산 후에 memo