フィボナッチ関数

7669 ワード
DP テキストリンク

白駿1003


ダイナミックプログラミングは、多くの時間、メモリが必要な場合に、サブ問題を解決し、結果を記録し、問題を解決する方法です.ダイナミックプランニングを習い始めたばかりで、もっと問題をしなければならないようです.

方法dynamic programming

n = int(input())
 
zero = [1,0]
one = [0,1]
 
def fibo(a):
    if len(zero) <= a:
        for i in range(len(zero), a+1):
            zero.append(zero[i-1] + zero[i-2])
            one.append(one[i-1] + one[i-2])
    print(zero[a], one[a])
 
for i in range(n):
    a = int(input())
    fibo(a)

関数なし

t = int(input())

dp_o = [1,0]
dp_l = [0,1]

for _ in range(t):
    n = int(input())
    if len(dp_o) <= n:
        for i in range(len(dp_o), n+1):
            dp_o.append(dp_o[i-1]+dp_o[i-2])
            dp_l.append(dp_l[i-1]+dp_l[i-2])
    print(dp_o[n], dp_l[n])
0の数字を参照してフィボナッチ数列を構成します.
参照1の数字もフィボナッチ数列を構成するので,それぞれのdpテーブルが形成される.

どうてきけいかくほう


多くの時間とメモリが必要な場合、サブ問題の解決、結果の記録、および問題の解決方法.
「再帰」関数を使用してフィボナッチを実装する場合は、時間がかかるため、参照0の数を表す「ゼロ」リストと
参照1の数字を表すリストを1つメモします.
どちらも入力した値が0と1の場合のみ表示されます.
fibo関数を実装する場合、リストの長さが入力した値以下である場合は、aに関するコメントがないため、どれだけ空欄にするかを示します.
そして,本来知るべき0[a]と1[a]を出力する.
リファレンス
1篇の文章は二叉木と二叉木をマスターして木を探します
[マイ・ハート]簡単なEメール検証コードの作成