Sections
People say that to tackle a big project, we should first break it up into smaller, easier mini-projects to work on individually, and then to bring the individual parts back together. Likewise, when we tackle problems, we should first break it up into smaller, easier problems to work on individually, and then to bring the individual parts back together.
But what if you could break it up into the same problem?
Recursion
You know that you can perform a linear search by checking the first element to the key, and then checking the second, and then so on.
But that’s equivalent to checking if the first element in the array to the key — and then doing the exact same thing with a new array with elements one through the end.
<span id="L1" class="line"><span class="cm">/* Performs a linear search.</span></span>
<span id="L2" class="line"><span class="cm"> * The array range is [begin, end) -- that is,</span></span>
<span id="L3" class="line"><span class="cm"> * begin is included but end is not.</span></span>
<span id="L4" class="line"><span class="cm"> */</span></span>
<span id="L5" class="line"><span class="kt">bool</span> <span class="nf">linear_search_iterative</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">begin</span><span class="p">,</span> <span class="kt">int</span><span class="o">*</span> <span class="n">end</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">)</span></span>
<span id="L6" class="line"><span class="p">{</span></span>
<span id="L7" class="line"> <span class="kt">int</span><span class="o">*</span> <span class="n">i</span> <span class="o">=</span> <span class="n">begin</span><span class="p">;</span> <span class="c1">//this will be our index</span></span>
<span id="L8" class="line"> <span class="k">do</span></span>
<span id="L9" class="line"> <span class="p">{</span></span>
<span id="L10" class="line"> <span class="c1">//if we find it, return true</span></span>
<span id="L11" class="line"> <span class="k">if</span> <span class="p">(</span><span class="o">*</span><span class="n">i</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span></span>
<span id="L12" class="line"> <span class="p">}</span> <span class="k">while</span> <span class="p">(</span><span class="o">++</span><span class="n">i</span> <span class="o">!=</span> <span class="n">end</span><span class="p">)</span> <span class="c1">//increment and check for end condition</span></span>
<span id="L13" class="line"> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span></span>
<span id="L14" class="line"><span class="p">}</span></span>
<span id="L15" class="line"></span>
<span id="L16" class="line"><span class="kt">bool</span> <span class="nf">linear_search_recursive</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">begin</span><span class="p">,</span> <span class="kt">int</span><span class="o">*</span> <span class="n">end</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">)</span></span>
<span id="L17" class="line"><span class="p">{</span></span>
<span id="L18" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">begin</span> <span class="o">==</span> <span class="n">end</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span> <span class="c1">//we've reached the end</span></span>
<span id="L19" class="line"> <span class="k">if</span> <span class="p">(</span><span class="o">*</span><span class="n">begin</span> <span class="o">==</span> <span class="n">key</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> <span class="c1">//we found it</span></span>
<span id="L20" class="line"> <span class="k">return</span> <span class="n">linear_search_recursive</span><span class="p">(</span><span class="n">begin</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">end</span><span class="p">,</span> <span class="n">key</span><span class="p">);</span> <span class="c1">//go on</span></span>
<span id="L21" class="line"><span class="p">}</span></span>Of course, it might not make so much sense to use recursion with such a simple problem whose iterative method is so intuitive. But with other problems, it certainly would make quite a bit of sense.
<span id="L1" class="line"><span class="cm">/* Performs a binary search on an ascending-sorted array.</span></span>
<span id="L2" class="line"><span class="cm"> * The array range is [begin, end) -- that is,</span></span>
<span id="L3" class="line"><span class="cm"> * begin is included but end is not.</span></span>
<span id="L4" class="line"><span class="cm"> */</span></span>
<span id="L5" class="line"><span class="kt">bool</span> <span class="nf">binary_search_iterative</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">begin</span><span class="p">,</span> <span class="kt">int</span><span class="o">*</span> <span class="n">end</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">)</span></span>
<span id="L6" class="line"><span class="p">{</span></span>
<span id="L7" class="line"> <span class="kt">int</span><span class="o">*</span> <span class="n">mid</span><span class="p">;</span></span>
<span id="L8" class="line"> <span class="k">while</span> <span class="p">(</span><span class="n">begin</span> <span class="o">!=</span> <span class="n">end</span><span class="p">)</span></span>
<span id="L9" class="line"> <span class="p">{</span></span>
<span id="L10" class="line"> <span class="c1">//choose our pivot.</span></span>
<span id="L11" class="line"> <span class="c1">//this is pointer arithmetic, and is legal.</span></span>
<span id="L12" class="line"> <span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">end</span> <span class="o">-</span> <span class="n">begin</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span> <span class="o">+</span> <span class="n">begin</span><span class="p">;</span></span>
<span id="L13" class="line"></span>
<span id="L14" class="line"> <span class="c1">//did we find it?</span></span>
<span id="L15" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o">==</span> <span class="o">*</span><span class="n">mid</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span></span>
<span id="L16" class="line"></span>
<span id="L17" class="line"> <span class="c1">//on which side is it?</span></span>
<span id="L18" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o"><</span> <span class="o">*</span><span class="n">mid</span><span class="p">)</span></span>
<span id="L19" class="line"> <span class="n">end</span> <span class="o">=</span> <span class="n">mid</span><span class="p">;</span></span>
<span id="L20" class="line"> <span class="k">else</span></span>
<span id="L21" class="line"> <span class="n">begin</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span></span>
<span id="L22" class="line"> <span class="p">}</span></span>
<span id="L23" class="line"></span>
<span id="L24" class="line"> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span></span>
<span id="L25" class="line"><span class="p">}</span></span>
<span id="L26" class="line"></span>
<span id="L27" class="line"><span class="kt">bool</span> <span class="nf">binary_search_recursive</span><span class="p">(</span><span class="kt">int</span><span class="o">*</span> <span class="n">begin</span><span class="p">,</span> <span class="kt">int</span><span class="o">*</span> <span class="n">end</span><span class="p">,</span> <span class="kt">int</span> <span class="n">key</span><span class="p">)</span></span>
<span id="L28" class="line"><span class="p">{</span></span>
<span id="L29" class="line"> <span class="c1">//check if we couldn't find it</span></span>
<span id="L30" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">begin</span> <span class="o">==</span> <span class="n">end</span><span class="p">)</span> <span class="k">return</span> <span class="nb">false</span><span class="p">;</span></span>
<span id="L31" class="line"></span>
<span id="L32" class="line"> <span class="c1">//choose pivot</span></span>
<span id="L33" class="line"> <span class="kt">int</span><span class="o">*</span> <span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">end</span><span class="o">-</span><span class="n">begin</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span> <span class="o">+</span> <span class="n">begin</span><span class="p">;</span></span>
<span id="L34" class="line"></span>
<span id="L35" class="line"> <span class="c1">//did we find it?</span></span>
<span id="L36" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o">==</span> <span class="o">*</span><span class="n">mid</span><span class="p">)</span> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span></span>
<span id="L37" class="line"></span>
<span id="L38" class="line"> <span class="c1">//do it again, but in the section we know it'll be in</span></span>
<span id="L39" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">key</span> <span class="o"><</span> <span class="o">*</span><span class="n">mid</span><span class="p">)</span> <span class="k">return</span> <span class="n">binary_search_recursive</span><span class="p">(</span><span class="n">begin</span><span class="p">,</span> <span class="n">mid</span><span class="p">,</span> <span class="n">key</span><span class="p">);</span></span>
<span id="L40" class="line"> <span class="k">return</span> <span class="n">binary_search_recursive</span><span class="p">(</span><span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="n">end</span><span class="p">,</span> <span class="n">key</span><span class="p">);</span></span>
<span id="L41" class="line"><span class="p">}</span></span>As you can probably see, with binary search (a divide-and-conquer algorithm), the recursive method is quite intuitive: the code speaks for itself.
"If the array’s empty (begin == end), then we didn’t find it.
Take the middle, and check if we found the key (key == *mid).
If we still didn’t find it, then check which side it’s on, and do the same with the appropriate side."
And for certain problems, the recursive approach is extremely simple to find. The archetypical example is to find a certain fibonacci number. The recursive solution is obvious, given just by the definition of a fibonnaci number:
<span id="L1" class="line"><span class="cm">/* Calculates the n-th Fibonacci number.</span></span>
<span id="L2" class="line"><span class="cm"> * The zeroeth Fibonacci number is 0 and the first is 1.</span></span>
<span id="L3" class="line"><span class="cm"> */</span></span>
<span id="L4" class="line"><span class="kt">unsigned</span> <span class="kt">int</span> <span class="nf">fib</span><span class="p">(</span><span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">n</span><span class="p">)</span></span>
<span id="L5" class="line"><span class="p">{</span></span>
<span id="L6" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o"><</span> <span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="n">n</span><span class="p">;</span></span>
<span id="L7" class="line"> <span class="k">return</span> <span class="n">fib</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">fib</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">);</span></span>
<span id="L8" class="line"><span class="p">}</span></span>|
Important
|
When you use recursion, you must make sure to cover every end case; recursive bugs tend to be difficult to isolate and fix. |
But you may have noticed a problem with this solution.
If you calculate fib(0) or fib(1), it takes exactly one iteration.
Calculating fib(2) takes three: once each for 2, 1, and 0.
Calculating fib(3) takes six: once each for 3 and 2, but twice each for 1 and 0.
You’ll notice an interesting pattern here: the number of iterations it takes to calculate fib(n) is the sum of the iterations it takes to calculate fib(n-1) and fib(n-2) plus one.
Essentially, this algorithm runs in exponential time. Its time complexity is \(\text{O}(2^n)\).
That’s not good.
Dynamic Programming
But notice that the reason that we have exponential time is that we calculate many of the same things multiple times.
We know that fib(n) is deterministic — that it always gives you the same output for the same input — so instead of recalculating everything all the time, why don’t we cache[1] those values so we can just look them up later?
This is called memoization[2].
So let’s add an array — a memo — for us to commit our results onto.
<span id="L1" class="line"><span class="cm">/* Calculates the n-th Fibonacci number.</span></span>
<span id="L2" class="line"><span class="cm"> * The zeroeth Fibonacci number is 0 and the first is 1.</span></span>
<span id="L3" class="line"><span class="cm"> * Uses memoization to achieve O(n) time complexity.</span></span>
<span id="L4" class="line"><span class="cm"> */</span></span>
<span id="L5" class="line"><span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">fib_ret</span><span class="p">[</span><span class="mi">1000</span><span class="p">]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">0</span><span class="p">};</span> <span class="c1">//declare memo, null initialize</span></span>
<span id="L6" class="line"><span class="kt">unsigned</span> <span class="kt">int</span> <span class="nf">fib</span><span class="p">(</span><span class="kt">unsigned</span> <span class="kt">int</span> <span class="n">n</span><span class="p">)</span></span>
<span id="L7" class="line"><span class="p">{</span></span>
<span id="L8" class="line"> <span class="c1">//have we calculated this already?</span></span>
<span id="L9" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">fib_ret</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">></span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="n">fib_ret</span><span class="p">[</span><span class="n">n</span><span class="p">];</span></span>
<span id="L10" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">n</span> <span class="o"><</span> <span class="mi">2</span><span class="p">)</span> <span class="k">return</span> <span class="n">fib_ret</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span></span>
<span id="L11" class="line"> <span class="k">return</span> <span class="n">fib_ret</span><span class="p">[</span><span class="n">n</span><span class="p">]</span> <span class="o">=</span> <span class="n">fib</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">fib</span><span class="p">(</span><span class="n">n</span><span class="o">-</span><span class="mi">2</span><span class="p">);</span></span>
<span id="L12" class="line"><span class="p">}</span></span>Our first check now is if we’ve found the answer, and now we achieve \(\text{O}(n)\) time complexity.
Here, we’re using 0 as the "nope we need to calculate" index, since the only call that will result that is fib(0), and so we don’t need to worry about redundancies.
Oftentimes it’s more useful to use -1 with signed ints; this can easily be achieved with memset():
<span id="L1" class="line"><span class="cp">#include <string.h></span></span>
<span id="L2" class="line"><span class="c1">//...</span></span>
<span id="L3" class="line"><span class="kt">int</span> <span class="n">memo</span><span class="p">[</span><span class="n">WHATEVER</span><span class="p">];</span></span>
<span id="L4" class="line"><span class="c1">//...</span></span>
<span id="L5" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span></span>
<span id="L6" class="line"><span class="p">{</span></span>
<span id="L7" class="line"> <span class="c1">//...</span></span>
<span id="L8" class="line"> <span class="n">memset</span><span class="p">(</span><span class="n">memo</span><span class="p">,</span> <span class="o">~</span><span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="o">*</span><span class="n">WHATEVER</span><span class="p">);</span></span>
<span id="L9" class="line"> <span class="c1">//...</span></span>
<span id="L10" class="line"><span class="p">}</span></span>"But Hans," you say, "couldn’t we just do this iteratively?"
And I say, "Yes, of course you can. Here’s the iterative version:"
<span id="L1" class="line">unsigned int fib(unsigned int n)</span>
<span id="L2" class="line">{</span>
<span id="L3" class="line"> unsigned int memo[n+1] = {0};</span>
<span id="L4" class="line"> memo[1] = 1;</span>
<span id="L5" class="line"> for (int i = 2; i <= n; ++i)</span>
<span id="L6" class="line"> memo[i] = memo[i-1] + memo[i-2];</span>
<span id="L7" class="line"> return memo[n];</span>
<span id="L8" class="line">}</span>But not all problems are so easy to move from the recursive method to the iterative method, and so it tends to be very useful to set up the recursive method and simply add the memo in to turn it into a DP approach.
An Example
Consider problem DP1P1: Maximum Sum.
Given an array of (positive) integers, find a subset with the maximal sum. However, there is the additional restriction that no two numbers in the subset may be adjacent.
For example, for the array
4 5 6 9 10:
4 6 10is valid, while5 9 10is invalid since 9 and 10 are next to each other.4 6 10happens to be the optimal sum in this case, so 20 is the answer.
— problem statement
dp1p1: Maximum Sum
dp1p1: Maximum Sum
Let \(a_i\) be the value of element \(i\) in the array.
We’ll define a function \(f(n)\) that is the maximum subset sum, given the restriction, for elements \([0,n)\)[3] of the array.
Obviously, \(f(0)=0\) and \(f(1)=a_0\): the maximum sum of the first zero elements is obviously zero and the maximum sum of the first element is just the first element.
We can see that \(f(n)=\max\Big(f(n-1), f(n-2)+a_{n-1}\Big)\). This makes sense, as either we use the maximal sum of the previous \(n-1\) elements and skip this element, or we use the maximal sum of the previous \(n-2\) elements and the current element[4], skipping the previous element and including the current element.
If we construct the code, it should look somewhat like this:
<span id="L1" class="line"><span class="cp">#include <stdio.h> //scanf(), printf()</span></span>
<span id="L2" class="line"></span>
<span id="L3" class="line"><span class="c1">//it's <algorithm> that has max(), but also so much also stuff</span></span>
<span id="L4" class="line"><span class="c1">//that might increase compile times and program size</span></span>
<span id="L5" class="line"><span class="kt">int</span> <span class="nf">max</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span></span>
<span id="L6" class="line"><span class="p">{</span></span>
<span id="L7" class="line"> <span class="k">return</span> <span class="p">(</span><span class="n">a</span><span class="o">></span><span class="n">b</span><span class="p">)</span><span class="o">?</span><span class="n">a</span><span class="o">:</span><span class="n">b</span><span class="p">;</span></span>
<span id="L8" class="line"><span class="p">}</span></span>
<span id="L9" class="line"></span>
<span id="L10" class="line"><span class="c1">//our array of numbers</span></span>
<span id="L11" class="line"><span class="kt">int</span> <span class="o">*</span><span class="n">arr</span><span class="p">;</span></span>
<span id="L12" class="line"></span>
<span id="L13" class="line"><span class="c1">//this is f(n) exactly as we defined earlier</span></span>
<span id="L14" class="line"><span class="kt">int</span> <span class="nf">max_firsts</span><span class="p">(</span><span class="kt">int</span> <span class="n">len</span><span class="p">)</span></span>
<span id="L15" class="line"><span class="p">{</span></span>
<span id="L16" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L17" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="n">arr</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span></span>
<span id="L18" class="line"> <span class="k">return</span> <span class="n">max</span><span class="p">(</span><span class="n">max_firsts</span><span class="p">(</span><span class="n">len</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">max_firsts</span><span class="p">(</span><span class="n">len</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">arr</span><span class="p">[</span><span class="n">len</span><span class="o">-</span><span class="mi">1</span><span class="p">]);</span></span>
<span id="L19" class="line"><span class="p">}</span></span>
<span id="L20" class="line"></span>
<span id="L21" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span></span>
<span id="L22" class="line"><span class="p">{</span></span>
<span id="L23" class="line"> <span class="c1">//get inputs</span></span>
<span id="L24" class="line"> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span></span>
<span id="L25" class="line"> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">n</span><span class="p">);</span></span>
<span id="L26" class="line"> <span class="n">arr</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">n</span><span class="p">];</span></span>
<span id="L27" class="line"></span>
<span id="L28" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span></span>
<span id="L29" class="line"> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="n">arr</span><span class="o">+</span><span class="n">i</span><span class="p">);</span></span>
<span id="L30" class="line"></span>
<span id="L31" class="line"> <span class="c1">//print output</span></span>
<span id="L32" class="line"> <span class="n">printf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="n">max_firsts</span><span class="p">(</span><span class="n">n</span><span class="p">));</span></span>
<span id="L33" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L34" class="line"><span class="p">}</span></span>This recursive solution works perfectly fine, but it has time complexity \(\text{O}(2^n)\). This occurs because we’ll be re-evaluating many of the same instances again and again, exactly like we were doing with the fibonacci algorithm. So let’s memoize:
<span id="L1" class="line"><span class="cp">#include <stdio.h> //scanf(), printf()</span></span>
<span id="L2" class="line"><span class="cp">#include <string.h> //memset();</span></span>
<span id="L3" class="line"></span>
<span id="L4" class="line"><span class="c1">//it's <algorithm> that has max(), but also so much also stuff</span></span>
<span id="L5" class="line"><span class="c1">//that might increase compile times and program size</span></span>
<span id="L6" class="line"><span class="kt">int</span> <span class="nf">max</span><span class="p">(</span><span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span></span>
<span id="L7" class="line"><span class="p">{</span></span>
<span id="L8" class="line"> <span class="k">return</span> <span class="p">(</span><span class="n">a</span><span class="o">></span><span class="n">b</span><span class="p">)</span><span class="o">?</span><span class="n">a</span><span class="o">:</span><span class="n">b</span><span class="p">;</span></span>
<span id="L9" class="line"><span class="p">}</span></span>
<span id="L10" class="line"></span>
<span id="L11" class="line"><span class="c1">//our array of numbers</span></span>
<span id="L12" class="line"><span class="kt">int</span> <span class="o">*</span><span class="n">arr</span><span class="p">;</span></span>
<span id="L13" class="line"><span class="c1">//the memo</span></span>
<span id="L14" class="line"><span class="kt">int</span> <span class="o">*</span><span class="n">memo</span><span class="p">;</span></span>
<span id="L15" class="line"></span>
<span id="L16" class="line"><span class="c1">//this is f(n) exactly as we defined earlier, but with memoization</span></span>
<span id="L17" class="line"><span class="kt">int</span> <span class="nf">max_firsts</span><span class="p">(</span><span class="kt">int</span> <span class="n">len</span><span class="p">)</span></span>
<span id="L18" class="line"><span class="p">{</span></span>
<span id="L19" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">memo</span><span class="p">[</span><span class="n">len</span><span class="p">]</span> <span class="o">>=</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">len</span><span class="p">];</span></span>
<span id="L20" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span> <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">len</span><span class="p">]</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L21" class="line"> <span class="k">if</span> <span class="p">(</span><span class="n">len</span> <span class="o">==</span> <span class="mi">1</span><span class="p">)</span> <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">len</span><span class="p">]</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span></span>
<span id="L22" class="line"> <span class="k">return</span> <span class="n">memo</span><span class="p">[</span><span class="n">len</span><span class="p">]</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">max_firsts</span><span class="p">(</span><span class="n">len</span><span class="o">-</span><span class="mi">1</span><span class="p">),</span> <span class="n">max_firsts</span><span class="p">(</span><span class="n">len</span><span class="o">-</span><span class="mi">2</span><span class="p">)</span> <span class="o">+</span> <span class="n">arr</span><span class="p">[</span><span class="n">len</span><span class="o">-</span><span class="mi">1</span><span class="p">]);</span></span>
<span id="L23" class="line"><span class="p">}</span></span>
<span id="L24" class="line"></span>
<span id="L25" class="line"><span class="kt">int</span> <span class="nf">main</span><span class="p">()</span></span>
<span id="L26" class="line"><span class="p">{</span></span>
<span id="L27" class="line"> <span class="c1">//get inputs</span></span>
<span id="L28" class="line"> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span></span>
<span id="L29" class="line"> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="o">&</span><span class="n">n</span><span class="p">);</span></span>
<span id="L30" class="line"> <span class="n">arr</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">n</span><span class="p">];</span></span>
<span id="L31" class="line"> <span class="n">memo</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">];</span></span>
<span id="L32" class="line"> <span class="n">memset</span><span class="p">(</span><span class="n">memo</span><span class="p">,</span> <span class="o">~</span><span class="mi">0</span><span class="p">,</span> <span class="k">sizeof</span><span class="p">(</span><span class="kt">int</span><span class="p">)</span><span class="o">*</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">));</span></span>
<span id="L33" class="line"></span>
<span id="L34" class="line"> <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">n</span><span class="p">;</span> <span class="o">++</span><span class="n">i</span><span class="p">)</span></span>
<span id="L35" class="line"> <span class="n">scanf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="n">arr</span><span class="o">+</span><span class="n">i</span><span class="p">);</span></span>
<span id="L36" class="line"></span>
<span id="L37" class="line"> <span class="c1">//print output</span></span>
<span id="L38" class="line"> <span class="n">printf</span><span class="p">(</span><span class="s">"%d"</span><span class="p">,</span> <span class="n">max_firsts</span><span class="p">(</span><span class="n">n</span><span class="p">));</span></span>
<span id="L39" class="line"> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span></span>
<span id="L40" class="line"><span class="p">}</span></span>And so, we have an \(\text{O}(n)\) solution to this problem.
|
Note
|
Your memo should have as many dimensions as the length of your parameter list; if you need two variables in the parameter list, they should both be accounted for. |
Practice
-
-
Hint: Consider using a sparse array
-
-
-
Hint: Consider using two-parameter recursion
-
1. "write down", "store temporarily"
2. not "memorization": we’re committing something to a memo, a cache, not to memory, which would imply that we’re uploading it to some database that we could access whenever we wanted or something. That would be equivalent to computer-generated hardcoding and would give you \(\text{O}(1)\) algorithms, which are neither interesting nor useful when you don’t have access to the data.
3. the first \(n\) elements
4. which is \(a_{n-1}\) due to zero-indexing