동적계획법(4) 총 정리

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

DP

1. Overlapping subproblem

• Problem을 작은 subproblem으로 분해
• 재귀와 차이점은 subproblem에 중복되는 문제가 발생하고, subproblem의 계산값을 재사용

2. Optimal substructure

• subproblem의 최적 해법으로 원래 문제의 최적 해법을 구할 수 있다.

구현방법

1. Top down (memoization) - 재귀
2. Bottom up (tablulation) - 반복문

차이점

• 코드 구현시 재귀 관계식과 기저조건이 필수
  f(n) = f(n-1) + f(n-2)

보통 문제풀이
완전탐색(재귀) -> DP(top down) -> DP(bottom up)