Level3_멀리뛰기

https://programmers.co.kr/learn/challenge_codes/153

풀이

1. 한 칸을 오르는 방법 : 1

2. 두 칸을 오르는 방법 : 2

3. 세 칸을 오르는 방법
   ​

    처음 한 칸 오르고 나머지 두 칸 오르는 방법 
   

   ​ + 처음 두 칸 오르고 나머지 한 칸 오르는 방법

4. 네 칸을 오르는 방법

    처음 한 칸 오르고 나머지 세 칸 오르는 방법
   

   ​ + 처음 두 칸 오르고 나머지 두 칸 오르는 방법

5. f(1) =1 / f(2) =2 / … / f(n+2) = f(n+1) + f(n)

개념

1. Dynamic Programming

   • 복잡한 문제를 간단한 문제로 나눠 푸는 방법.
   • 문제를 여러 하위 문제로 나눠 푼 다음, 그 결과를 이용하여 결합해 문제 해결

2. 피보나치 수열