Part7_도전과제(DynamicProgramming)_

문제

N개의 돌로 다리를 만들어 놓았다.
한번에 한칸 또는 두칸씩 건널 수 있음
개울을 건너는 방법의 가지수는?

1 2 3 4 5 6 7 + 도착지
ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ ㅁ + 도착지
첫번째 칸 가는 경우의 수 : 1
2번째 칸 가는 경우 : 2

1 2 3 4 5 6 7 + 마지막 도착지
1 2 3 5 8 13 21 >>> 34

3 번째 칸 가는 경우 :
1 1 1
1 2
2 1

4 번째 칸 가는 경우
1 1 1 1
1 1 2
1 2 1
2 1 1
2 2

이전 문제와 마찬가지로 풀이가능

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+2)
    DFS(n+1)

    print(dy[n+1])