2

任务定义：

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

小例子：

假设你有score 50并且matrix

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);
}

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

为什么它会消耗时间/内存：

还有一个问题：我需要存储路径集合并将其作为参数传递给循环方法。但是循环方法在每次迭代时都会分叉，我必须将路径集合复制一次迭代。否则，每个循环分支都会修改公共路径集合，最后我将拥有所有可能的路径。我的意思是如果在left, top&之间，diagonal最大的是left我们不能包含用topand链接的路径diagonal。

问题：

如何以正确的方式解决它？

编辑：

实际上没有必要找到完整的路径。它只需要找到您拨打分数的点（您在其中进行对角线移动）

4

2 回答 2

3

你不需要动态编程也不需要蛮力！

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

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

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

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

而已！

请注意，可能有多个最大路径，您的问题规范并不能保证唯一的解决方案。

编辑： 如果您不需要实际路径，而只需要您得分的数字，那么算法会容易得多 - 删除或忽略最后一行和最后一列，然后为每个i（行）返回该行中的最大值。

于 2013-11-04T21:59:24.603 回答
1

编辑：我将问题误读为只是向下和向右移动（即：j只能更改为j或j+1。）所以这个答案是错误的。

您可以使用动态规划来解决这个问题。贪婪并不完全有效，因为您只能“向下和向右”移动。

幼稚的动态编程解决方案本质上是从字面意义上“向后工作”，并从右下角开始，并在从该单元格开始时计算最大分数。

从右到左开始，从下到上，您可以简单地计算从该分数中获得的最佳分数。您对m x n矩阵执行此操作，然后从左上角开始并选择得分最高的方向。

于 2013-11-04T21:35:51.687 回答