Dynamic Programming 정리

11 Aug 2021 in Algorithms

다음과 같은 특징을 가지면 dynamic programming으로 구현할 수 있다.

1. Optimal Substructure (최적 부분 구조)
   • 큰 문제를 작은 문제로 나눌 수 있다.
2. Overlapping Subprobelm (중복되는 부분 문제)
   • 동일한 작은 문제를 반복적으로 해결

Top Down (메모이제이션)

• 한번 계산한 결과를 메모리 공간에 메모한다.
• 캐싱이라고도 한다.
• 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출해 ,그 문제가 해결됐을 때 큰 문제가 해결되게

Bottom Up

• 아래쪽에서 부터 작은 문제를 해결해 나가면서, 이 계산값을 사용해 다음 문제를 해결한다.

• 이게 다이나믹 프로그래밍의 전형적인 방식

• i번째의 최적의 해는, i-1번째의 최적의 해와 i-2번째의 최적의 해를 비교해서 풀어나가는 경우가 많다.

  a(i) = max(a(i-1),a(i-2)+ki)
  

참고 자료 - 동빈나님 유투브