문제 / 계단오르기(Top-Down : 메모이제이션) - 동적 계획법 / Python 파이썬

 

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

 

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

만약 총 4계단을 오른다면 그 방법의 수는

1+1+1+1,

1+1+2,

1+2+1,

2+1+1,

2+2

로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

▣ 입력설명

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

▣ 출력설명

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

▣ 입력예제 1

7

▣ 출력예제 1

21

---

나의 풀이 (동적 계획법)

def solution(n):
    dy = [0] * (n+1)
    dy[1] = 1 # 높이 1인 계단을 올라가는 방법 1칸씩 (1가지)
    dy[2] = 2 # 높이 2인 계단을 올라가는 방법 1칸씩 두번, 2칸씩 한번(2가지)
    for i in range(3,n+1):
        dy[i] = dy[i-1] + dy[i-2]
    return dy[n]

if __name__ == '__main__':
    n = int(input())
    print(solution(n))

 

---

※ 알아야 할 것

- 점화식 dy[i] = dy[i-1] + dy[i-2]