하위의 작은 문제들(subproblems)을 풀고, 이를 이용해서 더 큰 문제(original problem)를 풀어나가는 방법. 그런 의미에서 분할 정복법과 공통적 - obtimal structure

어떤 제한 조건이 주어졌을 때 무언가를 최적화하는 경우에 유용하다

하위 문제가 서로 의존하지 않는 경우에만 사용할 수 있다

답안에는 격자가 필요하다

격자의 각 칸에는 최적화하고자 하는 값을 적는다

각 칸은 원래 문제에 대한 하위 문제이다. 따라서 원래의 문제를 어떻게 하위 문제로 나눌 수 있을지 생각해야 한다

격자의 축을 생각한다

해답을 계산해주는 쉬운 공식은 없다. 직접 알아내야 한다

• 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다

• 주어진 문제에 대한 점화식을 정의한다(점화식으로 정의 될 수 있다면 DP로 해결) - 가장 중요

  

  bottom-up : 점화식에서 오른쪽 부분이 왼쪽 부분보다 먼저 계산 되는 순서를 의미한다

• 점화식을 memoization(top-down) 또는 bottom-up 방식으로 푼다 (크게는 둘 다 동적 계획법이지만, bottom-up만을 의미하는 경우도 있다. memoization을 쓰지 않고 recursion을 활용하면 중복 호출로 심각한 비효율이 발생한다)

  • top-down VS bottom-up

  둘의 시간 복잡도는 동일하다. 하지만 함수 호출시에 시간 소모가 일정 부분 더 되기 때문에 시간 복잡도 기준 input이 커지면 시간 차이가 크게 날 수 있다

  이런 예는 quickSort와 mergeSort에서도 확인해 볼 수 있는데, 이 둘 역시 시간복잡도가 동일하지만 시간 차이가 크게 나는 경우가 있다 (quickSort가 평균적으로 더 빠름)

  따라서 bottom-up이 평균적으로 시간 소모가 적다

• 전체 문제(주어진 문제)가 무엇인지 확인한다(n) -> dp[n]을 한글로 정의한다

• 1부터 i-1까지 채워진 값을 이용해 dp[i]에 대한 점화식을 세운다(1 ~ i-1까지의 값이 채워진 부분에 대해선 의심할 필요 없다, 뒤에 하나의 단위가 더 붙는다고 생각해도 괜찮다)

• 초기 조건 필요한지 체크

• 때에 따라 값이 커지기 때문에 dp[]의 타입을 long으로 한다, 값을 어떤 수로 나눈 나머지를 저장해야하는 경우 있다