dynamic-programming - 1 ～ 10^9 の値に dp を適用する

Question

1 から 10^9 までのフィボナッチ数を格納したい。DPを使用。配列の最大サイズがそれよりもはるかに小さい場合、これを行うにはどうすればよいですか。

Answer 1

ありえない。最大許容配列に格納できない場合、すべての数値を格納することはできません。単一の値のみを計算するためにすべての値を保存する必要はありませんが、必要な変数は 3 つだけです。また、見つけるための対数解がありますF(n)- フィボナッチのn番目の数。