我有一个n*n矩阵，其中每个元素代表一个整数。从头开始，[0,0]我必须找到精确m到最后一行的元素的路径，并返回最大成本。该路径可以在最后一行的任何列中结尾，并且n ≤ m ≤ n^2
n*n
[0,0]
m
n ≤ m ≤ n^2
我想到要找到m从[0,0]到的所有长度的路径[n-1, 0], [n-1, 1] ... [n-1, n-1]。但是感觉并不理想…
[n-1, 0], [n-1, 1] ... [n-1, n-1]
哪种算法是最有效的方法？是BFS还是DFS？
编辑
可能的方向是向下/向右/向左，但每个元素最多只能访问一次。
编辑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
m = n^2
[ → → → ↓ ] [ ↓ ← ← ← ] [ → → → ↓ ] [ x ← ← ← ]
编辑3 /解决方案
感谢WanderleyGuimarães， http：//ideone.com/0iLS2
您可以使用动态编程解决此问题。让value(i, j)值从(i, j)矩阵的位置开始（第i行，第j列）。
value(i, j)
(i, j)
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)
该递归假设您下台时使用矩阵中的头寸。因此，您的答案是max(f(m, 0), f(m-1, 1), f(m - 2, 2), ..., f(1, m))。
max(f(m, 0), f(m-1, 1), f(m - 2, 2), ..., f(1, m))
例如：
给出以下矩阵n = 4：
n = 4
1 1 1 1 1 2 1 1 2 1 1 1 1 2 1 1
如果那样的m = 2话，你不能在第二行之后。你的答案是f(2, 2) = 4。
m = 2
f(2, 2) = 4
如果那样的m = 4话，你不能去第三行。你的答案是f(3, 2) = 5。
m = 4
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)。 我正在努力改善它。
O(n^4)
您可以在http://ideone.com/tbH1j上对其进行测试
