dynamic-programming - 对 1-10^9 的值应用 dp

Question

我想存储 1-10^9 的斐波那契数。使用 dp。当数组的最大大小远小于该值时，如何做到这一点。

Answer 1

不可能。如果最大允许数组无法存储它们，则无法存储所有数字。但是，您不需要存储所有值来仅计算一个值 - 您只需要 3 个变量。还有一个对数解决方案可以找到F(n)- 第 n 个斐波那契数。