동적 계획법 (파이썬)

기본적인 접근 방식은 분할 정복 알고리즘과 비슷하다. 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결괏값을 이용해 원래 문제의 답을 산출한다. 그러나 동적 계획법은 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한 번 해당 문제를 풀 때에는 저장해둔 답을 바로 산출하여 속도를 향상한 것이다. 동적 계획벅을 구현하는 방법은 2가지가 있다. 하향식으로 문제를 풀어나가는 메모이제이션(Memoization) (주의 :메모라이제이션(Memorization) 아님!!) 상향식으로 문제를 풀어나가는 타뷸레이션(Tabulation) 즉, 계산했던 걸 저장한다라는 것이 핵심인 것이다. (캐싱이라고도 불림) 말로 하면 ..

원문링크 : 동적 계획법 (파이썬)