Dynamic Programming(DP) 란 ?
너무 방대한 문제에 대해서 문제를 작게 쪼개어서 해결하는 알고리즘
- DP는 항상 현재 가치를 최대가치로 생각 하고 저장 해놓기 때문에 다음 값이 이전보다 나빠지는 경우는 없다.
- DP는 쪼개어진 각 하위 문제들이 서로 의존성이 없을 때만 쓸 수 있다.
- 보통 점화식을 이용하여 답을 도출하는 경우가 많다.
메모이제이션
잘개 쪼개어진 문제들에 대해서 결과 값을 배열에 담아 저장 해두고 필요 할 때마다 꺼내 쓰는 방식
재귀를 사용하여 위에서 부터 아래로 문제를 쪼개 가면서 푸는 방식이다. 시간 복잡도를 감소 시키기 위해 메모이제이션을 사용한다.
아래에서 부터 위로, 처음 값부터 시작해서 원하는 문제의 답이 나올 때 까지 다음 값을 구하는 방법이다.