TIL_221129

Dynamic Programming

Top Down Approach

Base Case: Fib(0) = 0 and Fib(1) = 1
Recursive Step: Fib(n) = Fib(n-1) + Fib(n-2)

메모화 하지 않았을 경우에 반복되는 연산을 수행해서 원하는 결과에 도달하기까지 너무 많은 시간이 소요된다.

반복되는 sub-problem의 solution을 save(memorize) 하여 작업을 빠르게 할 수 있다. 즉 이 접근 방식은 분해를 사용하여 solution을 공식화한다. 재귀 함수에 바로 대입하여 결과가 정말 빠르게 나온다.

참고자료: https://www.simplilearn.com/tutorials/data-structure-tutorial/what-is-dynamic-programming