[Python] Dynamic Programming

동적 계획법

📌 참고 링크

이미 진행이 되었던 연산이 반복되는 결점을 보안하기 위해 동적 계획법이 고안되었다.

• 메모이제이션(Top-Down, 하향식)
• 테이블화(Bottom-Up, 상향식)

보통 어떤 문제에 적용?

소문제의 결과를 다른 소문제를 푸는데 사용되는 풀이법

• 동적 계획법: 소문제 종속적(소문제가 상위 문제에 영향을 끼치며 원소들이 종속적) / Always 최적의 결과 도출
• 분할 정복: 소문제 독립적(퀵정렬, 병합 정렬)
• 그리디: ‘현 상태’에 대해서 최적의 경우를 판단하므로 최적해가 구해지지 않을 수 있음