algorithm - 有趣的谜题

Question

任务定义:

我有一个自然数矩阵。任务是找到从矩阵左上角到矩阵右下角的路径并拨出最大分数。导航规则:如果您位于 [i][j]，您可以移动:a) 到 [i][j-1], [i][j+1], [i+1][j] 个单元格并拨零点b) 向[i+1][j+1]拨矩阵[i][j]点

小例子:

假设您有50分和矩阵

0 3 5 3 2
4 7 2 5 2
4 3 5 2 5

假设您在 [1][1] 个单元格中(矩阵 [1][1] = 7)。您可以导航到:

a) [1][0] cell with 50 score
b) [1][2] cell with 50 score
c) [2][1] cell with 50 score
d) [2][2] cell with 57 score

什么问题:

我以非常缓慢的方式解决这个任务...

我尝试在递归的帮助下实现。如果您只想找到最高分，这很容易。有点像

public int loop(int i, int j) {
  int left = loop(i, j-1);
  int top = loop(i-1, j);
  int diagonal = loop(i-1,j-1) + matrix[i-1][j-1];
  return maximum(left, top, diagonal);
}

但是，我想找到得分最高的路径!而且它非常耗时/内存。

为什么会耗费时间/内存:

还有一个问题:我需要存储路径集合并将其作为参数传递给循环方法。但是循环方法在每次迭代时 fork ，我必须在迭代时复制路径集合。否则，每个循环分支都会修改公共(public)路径集合，最后我将在其中包含所有可能的路径。我的意思是，如果在 left、top 和 diagonal 之间，最大的是 left，我们不能包含链接的路径顶部 和对角线。

问题:

如何正确解决？

编辑:

其实不需要找全路径。它只需要找到你拨分数的点(你在其中进行对角线移动)

Answer 1

为此您不需要动态规划或暴力破解!

要了解原因，让我们分析一下规则:

• 您可以在 j 方向上自由移动(左和右)，因此没有理由要小心那个方向 - 您可以随时移动到最佳水平位置。
• 一旦您增加了i(向下)就没有回头路了(尽管您可以增加i 而不会获得分数)。 i 的每次增加都应该获得最大的点数。
• 您可以通过离开一个单元格来获得积分，但是您只能离开一行一次。
• 这意味着你可以分割这个问题，不需要动态规划:你可以移动到最优的j位置，然后对角线走一步；重复直到完成。
• 最佳 i 步骤是从具有最高值的行中的非最后一个单元格开始移动。您不能从最后一个单元格移动，因为不可能进行对角线移动 - 因此，如果您的矩阵只有一列(或一行)，您将永远不会获得积分。您不会失分，因为这些值是自然数(但如果允许负数，您仍然可以跳过一行)。

更详细地说，然后通过...找到最佳路径

1. 矩阵是否只有一列或一行？反复向右移动没有获得积分然后结束程序。你不能在这里做很多事情。
2. 找到当前行中的最大值，忽略最后一个值。
3. 生成“j”向最大值单元格移动，然后沿对角线移动。
4. 如果您不在最后一行，请返回第 2 步。
5. 您在最后一行，无法获得更多积分；只需向右下角生成移动即可完成您的路径。

就是这样!

请注意，可能存在多个最大路径，您的问题说明并不能保证唯一的解决方案。

编辑:如果您不需要实际路径，而只需要您得分的数字，则该算法会简单得多 - 删除或忽略最后一行和最后一列，然后对于每个 i(行)返回该行中的最大值。