정답은 1번 동적 계획법(Dynamic Programming)입니다. 동적 계획법은 특정 문제를 해결할 때, 문제를 하위 문제로 나누고 그 하위 문제의 최적해를 이용하여 최종 문제의 최적해를 구하는 방법입니다. 따라서 주어진 조건에 부합합니다.