<h2id="speeding-up-fibonacci-with-dynamic-programming-memoization">Speeding up Fibonacci with Dynamic Programming (Memoization)<aclass="headerlink"href="#speeding-up-fibonacci-with-dynamic-programming-memoization"title="Permanent link">&para;</a></h2>

<p>Our recursive function currently solves fibonacci in exponential time. This means that we can only handle small input values before the problem becomes too difficult. For instance,<spanclass="arithmatex">$f(29)$</span> results in<em>over 1 million</em> function calls!</p>

<p>To increase the speed, we recognize that the number of subproblems is only<spanclass="arithmatex">$O(n)$</span>. That is, in order to calculate<spanclass="arithmatex">$f(n)$</span> we only need to know<spanclass="arithmatex">$f(n-1),f(n-2), \dots ,f(0)$</span>. Therefore, instead of recalculating these subproblems, we solve them once and then save the result in a lookup table. Subsequent calls will use this lookup table and immediately return a result, thus eliminating exponential work!</p>

<p>Each recursive call will check against a lookup table to see if the value has been calculated. This is done in<spanclass="arithmatex">$O(1)$</span> time. If we have previouslycalcuated it, return the result, otherwise, we calculate the function normally. The overall runtime is<spanclass="arithmatex">$O(n)$</span>. This is an enormous improvement over our previous exponential time algorithm!</p>

<p>Each recursive call will check against a lookup table to see if the value has been calculated. This is done in<spanclass="arithmatex">$O(1)$</span> time. If we have previouslycalculated it, return the result, otherwise, we calculate the function normally. The overall runtime is<spanclass="arithmatex">$O(n)$</span>. This is an enormous improvement over our previous exponential time algorithm!</p>

<divclass="highlight"><pre><span></span><code><spanclass="k">const</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">MAXN</span><spanclass="w"></span><spanclass="o">=</span><spanclass="w"></span><spanclass="mi">100</span><spanclass="p">;</span>

<spanclass="kt">bool</span><spanclass="w"></span><spanclass="n">found</span><spanclass="p">[</span><spanclass="n">MAXN</span><spanclass="p">];</span>

<spanclass="kt">int</span><spanclass="w"></span><spanclass="n">memo</span><spanclass="p">[</span><spanclass="n">MAXN</span><spanclass="p">];</span>

<ulclass="metadata page-metadata"data-bi-name="page info"lang="en-us"dir="ltr">

<spanclass="contributors-text">Contributors:</span>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (78.18%)</li><li><ahref="https://github.com/Zyad-Ayad"title="Zyad-Ayad"data-bi-name="contributorprofile"target="_blank">Zyad-Ayad</a> (9.7%)</li><li><ahref="https://github.com/clumsy"title="clumsy"data-bi-name="contributorprofile"target="_blank">clumsy</a> (5.45%)</li><li><ahref="https://github.com/ShubhamPhapale"title="ShubhamPhapale"data-bi-name="contributorprofile"target="_blank">ShubhamPhapale</a> (1.82%)</li><li><ahref="https://github.com/konstantinosalatzas"title="konstantinosalatzas"data-bi-name="contributorprofile"target="_blank">konstantinosalatzas</a> (1.21%)</li><li><ahref="https://github.com/Ahmed-Elshitehi"title="Ahmed-Elshitehi"data-bi-name="contributorprofile"target="_blank">Ahmed-Elshitehi</a> (1.21%)</li><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (1.21%)</li><li><ahref="https://github.com/tj91"title="tj91"data-bi-name="contributorprofile"target="_blank">tj91</a> (0.61%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (0.61%)</li></ul>

<ulclass="contributors"data-bi-name="contributors"><li><ahref="https://github.com/mhayter"title="mhayter"data-bi-name="contributorprofile"target="_blank">mhayter</a> (78.18%)</li><li><ahref="https://github.com/Zyad-Ayad"title="Zyad-Ayad"data-bi-name="contributorprofile"target="_blank">Zyad-Ayad</a> (9.7%)</li><li><ahref="https://github.com/clumsy"title="clumsy"data-bi-name="contributorprofile"target="_blank">clumsy</a> (4.85%)</li><li><ahref="https://github.com/konstantinosalatzas"title="konstantinosalatzas"data-bi-name="contributorprofile"target="_blank">konstantinosalatzas</a> (1.82%)</li><li><ahref="https://github.com/ShubhamPhapale"title="ShubhamPhapale"data-bi-name="contributorprofile"target="_blank">ShubhamPhapale</a> (1.82%)</li><li><ahref="https://github.com/Ahmed-Elshitehi"title="Ahmed-Elshitehi"data-bi-name="contributorprofile"target="_blank">Ahmed-Elshitehi</a> (1.21%)</li><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (1.21%)</li><li><ahref="https://github.com/tj91"title="tj91"data-bi-name="contributorprofile"target="_blank">tj91</a> (0.61%)</li><li><ahref="https://github.com/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (0.61%)</li></ul>