✺
동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중의 하나이다. 동적 계획법은 최적화 문제를 연구하는 수학이론에서 유래하였다. 전산학에서 흔히 쓰이는 dynamic, programming과는 관련이 없어서 혼동 할 수 있으므로 주의를 요한다. 중복을 회피하기 위한 기법 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 따르게 되는데 동적 계획법또한 divide&conquer방식을 이용해 주어진 문제를 작은 문제로 나눈뒤 답을 구하고 이 답들로부터 본 문제의 답을 구할 수 있다. 다만 분할 정복과 동적 계획법의 차이점으로는 문제를 나누는 방식이다. 문제를 나누게 될때 중복되는 부분이 문제마다 생길수도 안생길 수도 있는데, 데이터가 많아질 수록 중복되는