<p>你不应该计算斐波那契序列,甚至不应该用动态规划。由于斐波那契序列满足常系数、常阶的线性递推关系,因此它们的和序列也将满足线性递推关系</p>
<p>绝对不要缓存所有的值。这会给你不必要的内存消耗。当重复出现的顺序不变时,您只需记住重复出现顺序中的前几项即可</p>
<p>此外,还有一种方法可以将常阶循环转化为系统一阶循环。后者的解由矩阵的幂给出。这为<code>n</code>的大值提供了更快的算法。不过,每一步都会更加昂贵。因此,最好的方法将两者结合使用,第一种方法用于<code>n</code>的小值,第二种方法用于大输入</p>
<p><strong>O(n)对求和使用递归</p>
<p>表示<code>S_n=F_0+F_1+...+F_n</code>第一个斐波那契数的和<code>F_0,F_1,...,F_n</code></p>
<p>注意</p>
<ul>
<li><code>S_{n+1}-S_n=F_{n+1}</code></li>
<li><code>S_{n+2}-S_{n+1}=F_{n+2}</code></li>
<li><code>S_{n+3}-S_{n+2}=F_{n+3}</code></li>
</ul>
<p>因为<code>F_{n+3}=F_{n+2}+F_{n+1}</code>我们得到了<code>S_{n+3}-S_{n+2}=S_{n+2}-S_n</code>。所以</p>
<p><code>S_{n+3}=2S_{n+2}-S_n</code></p>
<p>初始条件为<code>S_0=F_0=1</code>、<code>S_1=F_0+F_1=1+1=2</code>和<code>S_2=S_1+F_2=2+2=4</code></p>
<p>您可以做的一件事是自下而上计算<code>S_n</code>,在每一步只记住前三项的值。您不需要记住<code>S_k</code>的所有值,从<code>k=0</code>到<code>k=n</code>。这将为您提供一个具有<code>O(1)</code>内存量的<code>O(n)</code>算法</p>
<hr/>
<p><strong>O(ln(n))通过矩阵求幂</strong></p>
<p>您还可以通过以下方式获得<code>O(ln(n))</code>算法:</p>
<p>调用<code>X_n</code>作为包含组件<code>S_{n+2},S_{n+1},S_{n}</code>的列向量</p>
<p>所以,上面的递推式给出了递推式</p>
<p><code>X_{n+1}=AX_n</code></p>
<p>其中<code>A</code>是矩阵</p>
<pre><code>[
[2,0,-1],
[1,0,0],
[0,1,0],
]
</code></pre>
<p>因此,<code>X_n=A^nX_0</code>。我们有{<cd26>}。要乘以<code>A^n</code>,我们可以做<a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow noreferrer">exponentiation by squaring</a></p>