다이나믹 프로그래밍

- 다음 두가지 조건을 만족하면 DP로 접근

1) 겹치는 부분 문제( overlapping subproblem )

2) 최적 부분 구조( optimal substructure )

- 같은 문제를 구할 때마다 정답은 같이 때문에 각 문제를 한 번만 풀어야 함

- 따라서 정답을 한 번 구하게 되면 배열에 저장하여 다시 쓰도록 함 -> 메모이제이션

cf. 템플릿 메타 프로그래밍과 비슷함 (템플릿 메타 프로그래밍은 컴파일 타이밍에 미리 만들어져서 알아서 쓰게 됨