DP는 Dynamic Programming(동적 계획법)으로 복잡한 문제를 더 작은 하위 문제로 만들어 계산해 위로 올라가는 방식이다. 개념은 재귀와 비슷하지만 재귀는 하향식, DP는 상향식이다. 즉 중복되는 계산을 저장하면서 올라가다보니 한번의 계산 후에 결과들을 저장하고 불러오는 형식이다. 또 최적의 값을 찾을 때도 사용한다. 문제를 풀기 위해서 메모와 점화식이 중요하다. 대표적인 문제는 피보나치 수열, 배낭 문제, 최단 경로, 최장 증가 부분, 문자열 편집 거리 등이 있다. DP의 장점은 중복 계산을 피할 수 있고 시간복잡도가 효율적이게 된다.하지만 단점으론 메모리 사용량이 상대적으로 크다. https://www.acmicpc.net/problem/9461 #include #include us..