큰 문제를 작은 문제로 나누고 작은 문제의 정답을 저장해 재사용해서 전체 문제를 최적(최소/최대/경우의 수)으로 푸는 기법. 하나의 문제는 단 한번만 풀어 여러번 다시 푸는 비효율적 중복 계산을 제거하는 알고리즘이다.성립 조건은 보통 두가지로 1. 겹치는 부분 문제 : 같은 작은 문제가 반복해서 등장한다.2. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해로 구성된다. DP를 푸는 과정 1. 테이블 정의하기2. 점화식 찾기 3. 초기값 정하기예제 1) 피보나치 문제https://www.acmicpc.net/problem/1003위 문제를 보면 1과 0의 갯수만 세면 문제가 풀릴거 같지만 주어진 시간이 0.25초로 제한 시간 초과로 문제를 틀리게 된다 .해당 주어진 식을 그대로 쓰지 않고 dp..