title: Dynamic Programming: Number of Seating Arrangements
body: <p>This was the bar-raiser question at a company I recently interviewed at. The premise is, a movie theatre has to follow a distance rule where every two seated individuals must have at least six feet distance between them. We are given a list of N non-negative integers where list[k] is the distance between seat k and seat k + 1 and a single row has N+1 seats. We need to figure out the number of valid seating arrangements.</p>
  <p>EDIT: After thinking about it more this is what I got so far</p>
  <pre><code>def count(seats):
      # No seats then no arrangements can be made
      if seats == 0:
          return 0
      elif seats == 1:
          # 1 seat means 2 arrangements -- leave it empty (skip) or occupy it
          return 2
      
      if list[seats-1] &lt; 6:
         return count(seats - 1) + counts(seats - k(seats))
      else:
         return count(seats - 1)
  </code></pre>
  <p>Recall that <strong>list</strong> will contain the distance between seat i and seat i+1 so at every seat I will check if the distance between the current seat and the previous one is &gt;= 6 or &lt; 6. If its less than 6 then I can skip the current seat or I can occupy it. Now here's the tricky bit, if I decide to occupy the seat my subproblem is not seats - 1, it will seats - (# of seats to skip to get to the next valid seat). I'm not sure how to find this one. The other case is more trivial, where the distance between the previous seat and current is &gt;= 6 so whether I occupy the current seat or not my subproblem, number of seats, shrinks by one.</p>