[파이썬] [DP] 예제2 철수의 계단

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면
그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

입력

첫째 줄은 계단의 개수인 자연수 N(3≤N≤45)이 주어집니다.

출력

첫 번째 줄에 올라가는 방법의 수를 출력합니다.

예제 입력 1

4

예제 출력 1

5

---

Top-Down 방식, 재귀

계단이 1일 때 -> 1
계단이 2일 때 -> 2 (1+1,2)
계단이 3일 때 -> 3 (1+1+1, 1+2, 2+1) 즉, 1번계단에서 2칸 뛰어서 왔거나, 2번계단에서 1칸 뛰어서 옴

F(n)=F(n-1)+F(n-2)

---

정답

Top-Down 방식

import sys

sys.stdin=open('input.txt','r')

if __name__=="__main__":
    n=int(input())
    dy=[0]*(n+1)                # 저장해 놓을 테이블을 정의한다
    dy[1]=1                     # 종이에 끄적이면서 점화식을 세운다.
    dy[2]=2                     # 규칙을 찾고 3번째 부터 적용되는 

    for i in range(3,n+1):
        dy[i]=dy[i-1]+dy[i-2]   # 점화식을 세운다.

    print(dy[n])

---