我有一个 N *ñ矩阵，其中重$ P $每个元素psents一个整数。开始于 [0,0] 我要找到确切的 M 元素到最后一排的路径，返回最大的成本。该路径可以在最后一行任何列结束， N≤M≤N ^ 2

I have a n*n matrix, where each element represents an integer. Starting in [0,0] I have to find the path of exactly m elements down to the last row, returning the maximum cost. The path can end in any column on the last row and n ≤ m ≤ n^2

我想找到长度的所有路径 M 从 [0,0] 到 [N-1，0]，[N-1，1] ... [n-1个，正 - 1] 。不过，这并不觉得最佳...

I thought of finding all paths of length m from [0,0] to [n-1, 0], [n-1, 1] ... [n-1, n-1]. But it does not feel optimal...

这算法是这样做的最有效的方法是什么？ BFS或DFS？

Which algorithm would be the most efficient way of doing this? BFS or DFS?

修改

可能的方向是下/左/右，但只能访问每个元素最多一次。

Possible directions are down/right/left, but only visit each element at most once.

编辑2

因此​​，例如，如果该矩阵给出（4例）：

So for example, if this matrix is given (n=4):

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

和M = 7，路径可能是

And m=7, the path could be

[   →   →   →   ↓ ]
[   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   ←   ←   ← ]

修改3 /解决方案：

由于Wanderley吉马良斯， http://ideone.com/0iLS2

Thanks to Wanderley Guimarães, http://ideone.com/0iLS2

推荐答案

您可以解决这个问题，动态规划。让值（I，J）从位置值（I，J）你的矩阵（第i行，第j列）。

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)

这是复发假设你从你的矩阵使用的位置，当你下台。所以，你的回答是最大（F（M，0），F（M-1,1），F（M - 2，2），...，F（1，M））。

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)).

例如：

给后续的矩阵 N = 4 ：

1 1 1 1
1 2 1 1
2 1 1 1
1 2 1 1

如果 M = 2 那么你不能二线后走了。而你的回答是 F（2,2）= 4 。

If m = 2 then you cant go after second line. And you answer is f(2, 2) = 4.

如果 M = 4 那么，你不能后三线走。而你的回答是 F（3,2）= 5 。

If m = 4 then you cant go after third line. And you answer is f(3, 2) = 5.

（林学英语，以便如果你不明白的东西让我知道，我将尽力提高我的解释）。的

修改::允许下/左/右移动

您可以实现如下复发：

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)

这个解决方案是为O（n ^ 4）。 我试着去改善它。的

您可以在 http://ideone.com/tbH1j