title: Understanding solution to finding optimal strategy for game involving picking pots of gold
body: <p>I am having trouble understanding the reasoning behind the solution to <a href="http://www.careercup.com/question?id=15422849" rel="noreferrer">this question on CareerCup</a>.</p>
  
  <blockquote>
    <p>Pots of gold game: Two players A &amp; B. There are pots of gold arranged
    in a line, each containing some gold coins (the players can see how
    many coins are there in each gold pot - perfect information). They get
    alternating turns in which the player can pick a pot from one of the
    ends of the line. The winner is the player which has a higher number
    of coins at the end. The objective is to "maximize" the number of
    coins collected by A, assuming B also plays optimally. A starts the
    game. </p>
    
    <p>The idea is to find an optimal strategy that makes A win knowing that
    B is playing optimally as well. How would you do that? </p>
    
    <p>At the end I was asked to code this strategy!</p>
  </blockquote>
  
  <p>This was a question from a Google interview.</p>
  
  <p>The proposed solution is:</p>
  
  <pre><code>function max_coin( int *coin, int start, int end ):
      if start &gt; end:
          return 0
  
      // I DON'T UNDERSTAND THESE NEXT TWO LINES
      int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))
      int b = coin[end] + min(max_coin(coin, start+1,end-1), max_coin(coin, start, end-2))
  
      return max(a,b)
  </code></pre>
  
  <p>There are two specific sections I don't understand:</p>
  
  <ol>
  <li>In the first line why do we use the ranges [start + 2, end] and [start + 1, end - 1]? It's always leaving out one coin jar. Shouldn't it be [start + 1, end] because we took the starting coin jar out?</li>
  <li>In the first line, why do we take the minimum of the two results and not the maximum?</li>
  <li>Because I'm confused about why the two lines take the minimum and why we choose those specific ranges, I'm not really sure what <code>a</code> and <code>b</code> actually represent?</li>
  </ol>