DP는 코딩테스트에 빈출되는 유형으로

기존의 재귀함수 시간과 공간 복잡도를 해결하고자 합니다.

재귀는 TOP DOWN 방식으로 스택에서 n부터 1까지 내려가는 방식이라면

DP는 bottom up 방식으로 거꾸로 1부터 n까지 올라가는 방식입니다.

이때 재귀는 지수거듭제곱으로 시간 복잡도가 증가되는 것을

DP를 활용하면 linear하게 줄일 수 있습니다

DP에 핵심은 1부터 n까지 계산 결과값을 배열에 저장해두고

이미 계산된 값은 다시 계산하지않고 배열에서 바로 가져오는 것입니다.

감사합니다.

내일은 DPS를 공부하겠습니다

- dc official App