동적 계획법(DP)

https://wooder2050.medium.com/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95-dynamic-programming-%EC%A0%95%EB%A6%AC-58e1dbcb80a0

1. 부분 문제 정의 (전체 문제를 작은 문제로 단순화)

2. 점화식 만들기 ( 재귀적인 구조를 활용할 수 있는 점화식 만들기)

3. 문제 해결 (작은 문제를 해결한 방법으로 전체 문제 해결)

메모이제이션(Memoization)은 동적계획법 핵심 개념이다. 함수의 리턴 값을 계산하고, 그 값을 저장소 역할을 하는 배열에 저장하는 방식이다. 이렇게 하면 함수를 매번 중복해서 호출하지 않고 이미 구한 값은 배열에서 O(1)로 가져올 수 있다.