동적 계획법: 당신이 생각하는 것이 아니다

알고리즘 학습에서 "동적 계획법"이라는 용어는 종종 혼란을 야기합니다. "동적"이란 그 변화성을 의미하는 것이 아니라 "계획"이라는 프로그래밍의 의미를 가리킵니다. 이는 1950년대 엔지니어들이 건설 프로젝트를 "프로세스 스케줄링"으로 계획했던 데서 유래합니다. 컴퓨터 과학에서 동적 계획법이란 문제를 해결하는 데 필요한 하위 단계의 순서를 계획하는 것을 의미합니다. 예를 들어 피보나치 수열을 계산하는 경우 "프로그램"이란 의존 관계 순서대로 fib(2)부터 fib(10)까지 계산하는 단계의 시퀀스입니다. 이는 상향식 또는 하향식으로 계획할 수 있습니다. 최종 계획은 동일하며, 둘 모두 동적 계획법으로 간주됩니다. 리처드 벨만은 국방 장관의 "수학 연구"에 대한 혐오감을 피하기 위해 이 용어를 만들었으며, "동적"이라는 형용사는 경멸적으로 사용할 수 없기 때문에 "동적 계획법"이라는 용어를 선택했습니다.