<liclass="md-nav__item">

<ahref="#dp-contests"class="md-nav__link">

<spanclass="md-ellipsis">

Dp Contests

DP Contests

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

Last update:

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">October11, 2024</span>&emsp;

<spanclass="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">October24, 2024</span>&emsp;

<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 previously calcuated 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 previously calcuated 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>

<spanclass="p">}</span>

<p>With our new memoized recursive function,<spanclass="arithmatex">$f(29)$</span>, which used to result in<em>over 1 million calls</em>, now results in<em>only 57</em> calls, nearly<em>20,000 times</em> fewer function calls! Ironically, we are now limited by our data type.<spanclass="arithmatex">$f(46)$</span> is the last fibonacci number that can fit into a signed 32-bit integer.</p>

<p>Typically, we try to save states in arrays,if possible, since the lookup time is<spanclass="arithmatex">$O(1)$</span> with minimal overhead. However, more generically, we can save statesanywaywe like. Other examples includemaps (binary search trees) orunordered_maps (hash tables).</p>

<p>Typically, we try to save states in arrays,if possible, since the lookup time is<spanclass="arithmatex">$O(1)$</span> with minimal overhead. However, more generically, we can save statesany waywe like. Other examples include binary search trees (<code>map</code> in C++) or hash tables (<code>unordered_map</code> in C++).</p>

<p>An example of this might be:</p>

<divclass="highlight"><pre><span></span><code><spanclass="n">unordered_map</span><spanclass="o">&lt;</span><spanclass="kt">int</span><spanclass="p">,</span><spanclass="w"></span><spanclass="kt">int</span><spanclass="o">&gt;</span><spanclass="w"></span><spanclass="n">memo</span><spanclass="p">;</span>

<spanclass="kt">int</span><spanclass="w"></span><spanclass="nf">f</span><spanclass="p">(</span><spanclass="kt">int</span><spanclass="w"></span><spanclass="n">n</span><spanclass="p">)</span><spanclass="w"></span><spanclass="p">{</span>

<p>This approach is called top-down, as we can call the function with a query value and the calculation starts going from the top (queried value) down to the bottom (base cases of the recursion), and makes shortcuts via memoization on the way.</p>

<h2id="bottom-up-dynamic-programming">Bottom-up Dynamic Programming<aclass="headerlink"href="#bottom-up-dynamic-programming"title="Permanent link">&para;</a></h2>

<p>Until now you've only seen top-down dynamic programming with memoization. However, we can also solve problems with bottom-up dynamic programming.

Bottomup is exactly the opposite of top-down, you start at the bottom (base cases of the recursion), and extend it to more and more values.</p>

Bottom-up is exactly the opposite of top-down, you start at the bottom (base cases of the recursion), and extend it to more and more values.</p>

<p>To create a bottom-up approach for fibonacci numbers, we initilize the base cases in an array. Then, we simply use the recursive definition on array:</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">int</span><spanclass="w"></span><spanclass="n">fib</span><spanclass="p">[</span><spanclass="n">MAXN</span><spanclass="p">];</span>

<p>Of course, as written, this is a bit silly for two reasons:

Firstly, we do repeated work if we call the function more than once.

Secondly, we only need to use the two previous values to calculate the current element. Therefore, we can reduce our memory from<spanclass="arithmatex">$O(n)$</span> to<spanclass="arithmatex">$O(1)$</span>.</p>

<p>An example of a bottomup dynamic programming solution for fibonacci which uses<spanclass="arithmatex">$O(1)$</span> might be:</p>

<p>An example of a bottom-up dynamic programming solution for fibonacci which uses<spanclass="arithmatex">$O(1)$</span> might be:</p>

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

<spanclass="kt">int</span><spanclass="w"></span><spanclass="n">fib</span><spanclass="p">[</span><spanclass="n">MAX_SAVE</span><spanclass="p">];</span>

<spanclass="w"></span><spanclass="k">return</span><spanclass="w"></span><spanclass="n">fib</span><spanclass="p">[</span><spanclass="n">n</span><spanclass="w"></span><spanclass="o">%</span><spanclass="w"></span><spanclass="n">MAX_SAVE</span><spanclass="p">];</span>

<spanclass="p">}</span>

<p>Note that we've changed the constant from<code>MAXN</code> TO<code>MAX_SAVE</code>. This is because the total number of elements we need tohaveaccess to is only 3. It no longer scales with the size of input and is, by definition,<spanclass="arithmatex">$O(1)$</span> memory. Additionally, we use a common trick (using the modulo operator) only maintaining the values we need.</p>

<p>That's it. That's the basics of dynamic programming: Don't repeat work you've done before.</p>

<p>Note that we've changed the constant from<code>MAXN</code> TO<code>MAX_SAVE</code>. This is because the total number of elements we need to access is only 3. It no longer scales with the size of input and is, by definition,<spanclass="arithmatex">$O(1)$</span> memory. Additionally, we use a common trick (using the modulo operator) only maintaining the values we need.</p>

<p>That's it. That's the basics of dynamic programming: Don't repeatthework you've done before.</p>

<p>One of the tricks to getting better at dynamic programming is to study some of the classic examples.</p>

<h2id="classic-dynamic-programming-problems">Classic Dynamic Programming Problems<aclass="headerlink"href="#classic-dynamic-programming-problems"title="Permanent link">&para;</a></h2>

<td>0-1knapsack</td>

<td>0-1Knapsack</td>

<td>Given<spanclass="arithmatex">$W$</span>,<spanclass="arithmatex">$N$</span>, and<spanclass="arithmatex">$N$</span> items with weights<spanclass="arithmatex">$w_i$</span> and values<spanclass="arithmatex">$v_i$</span>, what is the maximum<spanclass="arithmatex">$\sum_{i=1}^{k} v_i$</span> for each subset of items of size<spanclass="arithmatex">$k$</span> (<spanclass="arithmatex">$1 \le k \le N$</span>) while ensuring<spanclass="arithmatex">$\sum_{i=1}^{k} w_i \le W$</span>?</td>

<td>Subset Sum</td>

<td>Given<spanclass="arithmatex">$N$</span> integers and<spanclass="arithmatex">$T$</span>, determine whether there exists a subset of the given set whose elements sum up to the<spanclass="arithmatex">$T$</span>.</td>

<td>Longest Increasing Subsequence</td>

<td>Longest Increasing Subsequence (LIS)</td>

<td>You are given an array containing<spanclass="arithmatex">$N$</span> integers. Your task is to determine the LIS in the array, i.e., a subsequence where every element is larger than the previous one.</td>

<td>Countingall possible pathsin amatrix.</td>

<td>CountingPathsin a2D Array</td>

<td>Given<spanclass="arithmatex">$N$</span> and<spanclass="arithmatex">$M$</span>, count all possible distinct paths from<spanclass="arithmatex">$(1,1)$</span> to<spanclass="arithmatex">$(N, M)$</span>, where each step is either from<spanclass="arithmatex">$(i,j)$</span> to<spanclass="arithmatex">$(i+1,j)$</span> or<spanclass="arithmatex">$(i,j+1)$</span>.</td>

<li><ahref="https://leetcode.com/problems/maximal-square/description/">LeetCode - 221. Maximal Square</a></li>

<li><ahref="https://leetcode.com/problems/minimum-score-triangulation-of-polygon/description/">LeetCode - 1039. Minimum Score Triangulation of Polygon</a></li>

<h2id="dp-contests">Dp Contests<aclass="headerlink"href="#dp-contests"title="Permanent link">&para;</a></h2>

<h2id="dp-contests">DP Contests<aclass="headerlink"href="#dp-contests"title="Permanent link">&para;</a></h2>

<li><ahref="https://atcoder.jp/contests/dp/tasks">Atcoder - Educational DP Contest</a></li>

<li><ahref="https://cses.fi/problemset/list/">CSES - Dynamic Programming</a></li>

<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> (80.61%)</li><li><ahref="https://github.com/Zyad-Ayad"title="Zyad-Ayad"data-bi-name="contributorprofile"target="_blank">Zyad-Ayad</a> (11.52%)</li><li><ahref="https://github.com/jakobkogler"title="jakobkogler"data-bi-name="contributorprofile"target="_blank">jakobkogler</a> (2.42%)</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/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</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/boredumbk"title="boredumbk"data-bi-name="contributorprofile"target="_blank">boredumbk</a> (0.61%)</li><li><ahref="https://github.com/hitarth-gg"title="hitarth-gg"data-bi-name="contributorprofile"target="_blank">hitarth-gg</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> (79.39%)</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> (6.06%)</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/adamant-pwn"title="adamant-pwn"data-bi-name="contributorprofile"target="_blank">adamant-pwn</a> (0.61%)</li></ul>