10826:フィボナッチ数4

フィボナッチ数5は既に解決されていたので,コードをそのまま入れるとランタイムエラーが発生した.

Pythonの再帰深さのデフォルト値が1000に設定されているためです.

初めてやったことは復帰の深さを和らげることです。

(問題で要求されるnは10000であるため、制限は100000に増加する.)
(制限を増やしても、あまり深い再帰は実行されません(正しくありません).

import sys
sys.setrecursionlimit(100000)
def fibonacci(first_num, second_num, count) :
    tmp = first_num + second_num
    count -= 1

    if (count > 0) :
        return fibonacci(first_num = second_num,second_num= tmp, count= count)

    else :
        return tmp

n = int(input())

first = 0
second = 1
if(n == 0) :
    print(0)
elif(n==1) :
    print(1)
else :
    result = fibonacci(first_num= first, second_num= second, count= n - 1)
    print(result)

その結果、メモリオーバーフローが発生しました.

2回目の試みは、ネット上で見つけた動的計画法です。

ダイナミックプランニング

簡単に言えば、大きな問題を次のような問題に分けて解決することです。

もっと分かりやすいのは、1つの問題は1回しかできないことです.
△特にフィボナッチ数列では、これが有効です.
上のフィボナッチ関数は指数形式の時間複雑度を有する.(約2^n)
だからある程度の大きな数字を入れるとプログラムが跳ね返る….

そこで,注釈(Memoization)技術を採用した.

我々が計算したFibonacci(2),Fibonacci(3)...再計算せずに関数(など)を呼び出します.

計算した関数の値を任意のスペースに格納し、再書き込みします。

これにより,関数再計算を呼び出す必要がなくなるので,指数形式の時間的複雑さをO(N)に著しく低減できる.
(fibonacci(10000)の場合は、10000回計算して保存した値を使用するだけです!)

# 재귀함수로는 메모리 초과, 시간 초과로 풀리지 않는다. 
# fibonacci의 10000 번째 수는 생각보다 훨씬 더 큰 수였다..
# 이런 식으로 정보를 저장하며 풀어나가는 것을 동적계획법(Dynamic Programming)이라고 했다.
def fibonacci(count) :
    first_num = 0
    second_num = 1

    for i in range(count) :
        first_num, second_num = second_num, (first_num + second_num)

    return first_num

n = int(input())

if(n == 0) :
    print(0)
elif(n==1) :
    print(1)
else :
    result = fibonacci(count= n)
    print(result)

このコードで10826:フィボナッチ数4の問題を解決しました!
ダイナミックプランニング法の概念「大問題小問題解決」.この言葉はよく聞いたことがあるようですが、私は本当にどのように割って、どんな方法で解決するか分かりません.
私はもっと多くの問題をして、私に合った方法でそれを熟知します.