재귀함수형태로 점화식이 생기는 문제에서 일대일함수임이 만족될때 각 함수의 파라미터를 키로 결과를 캐싱하는걸 dp라함 이때 캐싱하는 자료구조를 편의상 상태공간이라 부르는데 별 의미는 없고 동적계획법(Dynamic programming)은 자료구조에서 동적할당(Dynamic Allocation)과는 다르다. 알고리즘에서 사용되는 "다이나믹(Dynamic)"은 별다른 의미 없이 사용된 단어이다. 다이나믹 프로그래밍 문제인지 확인하려면 아래 조건을 만족하는지 확인하면 된다. 1. 최적 부분구조(Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) : 동일한 작은..
