[알고리즘] 다이나믹 프로그래밍

DP의 핵심 개념과 종류

dp의 핵심은 중복되는 연산을 줄이는 것이다.
여기서 2종류로 나뉘는데 탑다운과 바텀업이 있다.

탑다운과 바텀업

1. 탑다운: 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출함
2. 바텀업: 작은 문제부터 차근차근 쌓아 올라가는 방식

dp가 쓰일 수 있는 조건

1. 문제를 부분 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

dp 문제시 최대한 바텀업 방식으로 구현하는 것이 좋다.

재귀 함수의 스택 크기가 한정적일 수 있기 때문!!!!