[알고리즘] Dynamic Programming

다이나믹 프로그래밍 요새 공부중인데 어렵다.

DP는 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.

DP 조건

  1. Overapping Subproblem
    부분 문제들이 중복된다.
  2. Optimal Substitue
    부분 문제의 최적의 해가 큰 문제의 최적의 해가 된다.

Top Down 하향식과 Bottom Up 상향식이 있다.
하향식은 재귀, 상향식은 반복문을 이용한다.
반복문이 오버헤드도 발생하지 않고, 속도가 재귀보다 더 빠르다.

DP로 문제를 풀때 순회적인 관계를 명시적으로 표현하기 위해서 점화식을 사용한다.

대표적인 DP문제로는 0-1 Knapsack, 최장증가수열 등의 문제가 있다.