77)계단오르기(Top-Down: 메모이제이션)

문제

총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인지 구하기

 

조건

수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다.

 

만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.

 

제한사항

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

 

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

 

문제풀이

def go(len):
  if dy[len]>0:
    return dy[len]

  if len==1 or len==2:
    return len

  else:
    dy[len]=go(len-1)+go(len-2)
    return dy[len]

N=int(input())
dy=[0]*(N+1)
dy[1]=1
dy[2]=2
print(go(N))