Dynamic Progamming

• Reference
• 가장 중요한 3가지가 있다. 이를 만족하면 DP 문제다.
  • 1. Problem을 Sub Problem으로 나눌 수 있는가
  • 2. Sub Problem으로 Problem을 구할 수 있는가
  • 3. SUb Problem이 겹치는게 있는가 (Memorization으로 해결)
    • Memorization 또는 DP Table의 경우 Array를 이용한다.
• 방식에는 2가지가 있다.
  • Top Down : 보통 Recursive로 풀며 Call Stack Overflow에 주의한다.
  • Bottom UP : 그래서 보통 O(n)으로 안전하게 해결할 수 있는 Bottom-up 방식을 주로 이용한다.
    • [F(0), F(1), F(2) .... , F(10000000000000000))]
    • Array 형태로 쌓아나가면 Space Complexity가 O(n)이지만 피보나치의 경우나 두 원소로 해결되면 해당 위치에 계속 써내려가면 되므로 O(1)로 해결 가능하다.