Dynamic Programming

DP

DP 정리

1. 하나의 문제가 서브 문제로 나뉘어지고
2. 나뉘어진 서브문제를 통해 값을 도출해낼 수 있어야 하며
3. 서브문제가 중복될때 메모이제이션을 통해 해결할 수 있는 기법

다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다.

이미 계산된 결과(서브 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다.

다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다.