Part7.3_2_동적프로그래밍(DynamicProgramming)_도전과제(Top-Down: 재귀, 메모이제이션)

문제

철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면
그 방법의 수는
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

bottom-up 방식

import sys
sys.stdin=open("input.txt","rt")
def input():
    return sys.stdin.readline().rstrip()

n = int(input())
dy = [0]*(n+1)
dy[1] = 1
dy [2] = 2
for i in range(3,n+1):
    dy[i] = dy [i-1] + dy[i-2] 
print(dy[n])

top-down 방식

import sys

sys.stdin=open("input.txt","rt")

def input():
    return sys.stdin.readline().rstrip()

def DFS(len):
    if dy[len] > 0:
        return dy[len]
    if len == 1 or len == 2:
        return len
    else:
        dy[len]=DFS(len-1)+DFS(len-2)
        return dy[len]

if __name__ == "__main__":
    n = int(input())
    dy = [0]*(n+1)
    DFS(n)

    print(dy[n])