title: Algorithm to traverse a grid collecting as many points as possible
body: <p>Consider a 2-dimensional m*n grid where each cell can contain either a 1 or a 0. Find the greatest value a traversal can acquire by moving through this grid. The value can be increased by traversing diagonally through a 1 cell. A traversal of the grid obeys the following rules:</p>
  
  <ol>
  <li>Start at the top-left cell.</li>
  <li>At each cell the traversal may move down one grid, move right one grid, or move diagonally (move down one grid and move right one grid). If the cell contains a 1 and the traversal moves diagonally then the traversal value increases by 1.</li>
  <li>The traversal cannot move off the grid (if at the right edge cannot move right, if at the bottom edge cannot move down).</li>
  <li>End at the lower right corner.</li>
  </ol>
  
  <p>A naive algorithm would consider all 3*m*n traversals and pick the largest value. Can someone help me come up with a better solution? Is there an algorithm that solves a similar problem?</p>
  
  <p>This isn't an interview question, I need this to try to optimize the Smith-Waterman algorithm.</p>
  
  <h3>Examples:</h3>
  
  <p>The following grid has a maximum value of 2:</p>
  
  <p><img src="https://i.stack.imgur.com/r7uv8.jpg" alt="enter image description here"></p>
  
  <p>This one has a maximum value of 7:</p>
  
  <p><img src="https://i.stack.imgur.com/rY0Ar.jpg" alt="enter image description here"></p>