у меня естьn*n матрица, где каждый элемент представляет целое число. Начиная в[0,0] Я должен найти путь точноm элементы до последней строки, возвращая максимальную стоимость. Путь может заканчиваться любым столбцом в последней строке иn ≤ m ≤ n^2

Я думал найти все пути длиныm от[0,0] в[n-1, 0], [n-1, 1] ... [n-1, n-1], Но это не чувствует себя оптимальным ...

Какой алгоритм будет наиболее эффективным способом сделать это? BFS или DFS?

EDIT

Возможные направления: вниз / вправо / влево, но посещать каждый элемент не более одного раза.

EDIT 2

Так, например, если эта матрица задана (n = 4):

[   1   4   1  20 ]
[   5   0   2   8 ]
[   6   8   3   8 ]
[   3   2   9   5 ]

И m = 7, путь может быть

[   →   →   →   ↓ ]
[   5   0   2   ↓ ]
[   6   8   3   ↓ ]
[   3   2   9   x ] = Path cost = 47

или же

[   ↓   4   1  20 ]
[   ↓   0   2   8 ]
[   →   →   ↓   8 ]
[   3   2   →   x ] = Path cost = 32 

или еслиm = n^2

[   →   →   →   ↓ ]
[   ↓   ←   ←   ← ]
[   →   →   →   ↓ ]
[   x   ←   ←   ← ]

EDIT 3 / SOLUTION

Благодаря Wanderley Guimar & es,
http://ideone.com/0iLS2