title: Algorithm to find max cost path of length N in matrix, from [0,0] to last row
body: <p>I have a <code>n*n</code> matrix, where each element represents an integer. Starting in <code>[0,0]</code> I have to find the path of exactly <code>m</code> elements down to the last row, returning the maximum cost. The path can end in any column on the last row and <code>n ≤ m ≤ n^2</code></p>
  
  <p>I thought of finding all paths of length <code>m</code> from <code>[0,0]</code> to <code>[n-1, 0], [n-1, 1] ... [n-1, n-1]</code>. But it does not feel optimal...</p>
  
  <p>Which algorithm would be the most efficient way of doing this? BFS or DFS?</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Possible directions are down/right/left, but only visit each element at most once.</p>
  
  <p><strong>EDIT 2</strong></p>
  
  <p>So for example, if this matrix is given (n=4):</p>
  
  <pre><code>[   1   4   1  20 ]
  [   5   0   2   8 ]
  [   6   8   3   8 ]
  [   3   2   9   5 ]
  </code></pre>
  
  <p>And m=7, the path could be</p>
  
  <pre><code>[   →   →   →   ↓ ]
  [   5   0   2   ↓ ]
  [   6   8   3   ↓ ]
  [   3   2   9   x ] = Path cost = 47
  </code></pre>
  
  <p>or</p>
  
  <pre><code>[   ↓   4   1  20 ]
  [   ↓   0   2   8 ]
  [   →   →   ↓   8 ]
  [   3   2   →   x ] = Path cost = 32 
  </code></pre>
  
  <p>or if <code>m = n^2</code></p>
  
  <pre><code>[   →   →   →   ↓ ]
  [   ↓   ←   ←   ← ]
  [   →   →   →   ↓ ]
  [   x   ←   ←   ← ]
  </code></pre>
  
  <p><strong>EDIT 3 / SOLUTION</strong></p>
  
  <p>Thanks to Wanderley Guimarães,<br>
  <a href="http://ideone.com/0iLS2" rel="nofollow">http://ideone.com/0iLS2</a></p>