고등학교 수학1 단원에서 배운 수학적 귀납법 개념을 프로그래밍에 적용시킨게 dynamic programming이다.
초기값(base)을 설정해주고, 점화식을 구해 임의의 N에 대해 모든 값을 구할 수 있도록 설계한다.
수학적 직관이 있으면 점화식을 생각할 때 매우 유리하다. 다소 발상적인 부분도 있어 알고리즘을 처음 접하는 경우라면 연습이 많이 필요하다. 관련 문제를 많이 많이 풀어보자.
반복문과 재귀 모두 사용할 수 있다. dp에서 중요한건 설정한 값에 대한 이해와 점화식... 여기서 반복문과 재귀는 구현하기 위한 도구로만 사용된다.
dp에서는 중복되는 계산을 줄이는 기법을 사용하는데, 재귀함수를 통해 dp를 구현할 때는 Memoization을 사용하고, 반복문을 통해 dp를 구현할 때는 Tabulation을 사용한다.
특정 배열을 하나 선언하고 값을 저장해 중복되는 계산을 피한다는 목적은 같다.
메모이제이션은 Top - Down / 타뷸레이션은 Bottom - Up 이라고도 하는데.. 용어보다는 로직에 집중하자.
dp의 기본 개념은 저게 다인데 변형문제가 매우 많다.
dp배열의 원소가 뭘 의미하는지 / 점화식은 어떻게 작성되는지. 이 두 가지에 집중해 dp를 공부하자.