[알고리즘/백준] 2748번 : 피보나치 수 2(python)

dp를 이용해서 구하면 된다... 점화식을 생각해야 해서 dp는 어려운듯 하다.

def fibo_dp(num):
    cache = [0 for _ in range(num + 1)]
    cache[0] = 0
    cache[1] = 1

    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]


if __name__ == "__main__":
    print(fibo_dp(int(input())))