개념

• 점화식을 짜서 문제를 해결하는 느낌이다.
• 완전탐색을 하되, 메모이제이션을 해서 불필요한 중복을 최대한 없애나간다.

사용할 수 있는 조건

• 참조투명성을 가지며, 입력을 제외한 외적 요소에 결과값이 영향을 미치면 안된다.

  • 대부분의 코딩테스트에서는 해당 안되는 이야기이다.

• 겹치는 부분문제가 존재한다.

  • 아래와 같은 경우를 말한다.

    

• 지역의 최적해가 전역의 최적해가 된다.

  • 그리디랑 비슷한 개념이다.

• 코딩테스트에서는 다음과 같은 사고로 쓸지 안쓸지 결정한다.

  • 완전탐색을 시도한다.
    • 경우의 수가 꽤 할만하다 → 완전탐색
    • 경우의 수가 좀 크다.
      • 메모이제이션을 시도한다.
        • 배열에 담을 만 하다 (100만개 이하이다) → DP
        • 배열에 담기 좀 힘들다 → 그리디