You can solve this problem with dynamic programming. Let value(i, j)
the value from position (i, j)
of your matrix (i-th line, j-th column).
if i < 0 then f(i, j) = 0
if i == 0 then f(i, j) = value(i, j)
if i > 0 then f(i, j) = max(f(i-1, j), f(i, j-1)) + value(i, j)
That recurrence assume that you use a position from your matrix when you step down. So, you answer is max(f(m, 0), f(m-1, 1), f(m - 2, 2), ..., f(1, m))
.
For example:
Give the follow matrix for n = 4
:
1 1 1 1
1 2 1 1
2 1 1 1
1 2 1 1
If m = 2
then you cant go after second line. And you answer is f(2, 2) = 4
.
If m = 4
then you cant go after third line. And you answer is f(3, 2) = 5
.
(Im learning english so If you didnt understand something let me know and I will try to improve my explanation).
Edit :: allow down/left/right moves
You can implement follow recurrence:
if i == n, j == n, p == m, j == 0 then f(i, j, p, d) = 0
if d == DOWN then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j-1, p+1, RIGHT), f(i, j+1, p+1,LEFT)) + value(i, j)
if d == LEFT then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j+1, p+1, LEFT )) + value(i, j)
if d == RIGHT then f(i, j, p, d) = max(f(i+1, j, p+1, DOWN), f(i, j-1, p+1, RIGHT)) + value(i, j)
This solution is O(n^4)
. Im trying to improve it.
You can test it at http://ideone.com/tbH1j