DP

문제 풀이 전략

점화식의 정의를 세우자.

• 글로 나타내자. 내가 어떤 문제를 풀려고 하는지 적자.

  • 예컨대, 피보나치 수열은 N번째 피보나치 수를 구하고 싶은 거임.

  • D[N] : N번째 피보나치 수

• 그다음, 어떻게 문제를 작은 문제로 나타낼 수 있는지 써보자.

  • N -> N-1, N-2

• 작은 문제를 만들었으면 어떻게 원래 문제를 풀 수 있는지 알아보자.

  • N번째 피보나치 수는 N-1번쨰 피보나치 수와 N-2번째 피보나치 수를 더한다.

  • D[N] = D[N-1] + D[N-2]

Fn = Fn-1 + Fn-2