Dynamic Programming

• It refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner

• 복잡한 문제를 풀때 부분 문제로 쪼갠다. 그리고 그 작은 문제들을 반복해서 푸는데, 반볷되는 풀이를 저장해두었다가 재사용(recursive)하는 기법.

  동적프로그래밍 조건

1. 최적부분구조(Optimal Substructure)

2. 중복 문제(Overlapping Subproblem)

   종류

   1 . Memoization

• Top-down 방식으로,쿤 문제에서 분할된 작은 문제들을 풀 때 반복해서 풀지 않고 memo라고 불리는(or note to self) 함수(재귀함수)를 만들어 놓고 푼다.

• 실행할때마다 함수를 호출하기 때문에, stack이 쌓여 오류가 날 수 있다.

  

  2 . Tabulation

• Bottom-up 방식으로 반복문으로 푼다.
  

• 공통점: 중복되는 부분 문제의 비효율을 해결

• 차이점: Memoization는 재귀함수를 이용하고, Tabulation는 반복문을 사용한다.