动态编程获得最大的钻石

Question

我试图解决一个面试问题：

给定n * n的矩阵。每个单元格包含0,1，-1。 0表示没有钻石，但有一条路径。 1表示在该位置处存在菱形，其中路径-1表示路径被阻挡。现在你从0,0开始到达最后一个单元格，然后返回到0,0收集最大的钻石数量。在前往最后一个单元格时，您只能向右和向下移动。返回时，您只能向左和向上移动。

我已经解决了这个问题，但我不确定这是最佳解决方案。我在做什么

• 这不是从最后一个单元格返回到第一个单元格，而是允许从初始单元格到最后一个单元格的2次迭代。
• 当我第一次迭代时，我将尝试使用动态编程获得最大数量的钻石，之后我将从矩阵中删除第一次迭代中收集的钻石，即：从1设置矩阵值0。
• 在第二次迭代中，我将调用与第一次迭代相同的方法，但使用修改后的矩阵。
• 并返回两个调用的总和。

有关正确性的任何建议吗？我写了代码，如果需要，我会分享。

Answer 1

你的算法不正确。这是一个反例：

<table border="1">
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
  <tr>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
   <tr>
    <td>0</td>
    <td>1</td>
    <td>1</td>
  </tr>
</table>

从上到下的最大路径将收集5颗钻石，可能是这样的：

<table border="1">
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
  <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
   <tr>
    <td>_</td>
    <td>_</td>
    <td>*</td>
  </tr>
</table>

但是你的第二次迭代只能再收集2次。

因此，您的算法将返回最大值7。

但是有一个解决方案，您可以用它来收集8。

例如。如果你的路径看起来像这样：

<table border="1">
  <tr>
    <td>*</td>
    <td>_</td>
    <td>_</td>
  </tr>
  <tr>
    <td>*</td>
    <td>*</td>
    <td>_</td>
  </tr>
   <tr>
    <td>_</td>
    <td>*</td>
    <td>*</td>
  </tr>
</table>

Answer 2

您可以使用动态编程。您需要填充矩阵，其大小为[2 * n-1，n，n]其中DP [A，B，C]等于对角线（或总路长度）A的最佳结果，第一路进入位置B，第二路进入位置C 。

你从DP [0,0,0]开始并结束到DP [2 * n-1,0,0]答案是DP [2 * n-1,0,0]

DP [l，i，j] = MAX（DP [l-1，i，j]，DP [l-1，i-1，j]，DP [l-1，i，j-1]，DP [ l-1，i-1，j-1]）+ Diamond [i，li] + Diamond [j，lj]，如果i等于j，则由Diamond [j，lj]减少。

并跳过所有无法通行的地方。

总复杂度为O（N ^ 3）

Answer 3

“你从0,0开始到达最后一个单元格，然后返回到0,0”

==“你从0,0开始到达最后一个细胞两次”

和

d：总分

x1：x位置为第一个

x2：x位置为秒

y1：x - x1 //可以省略

y2：dx - x2 //可以省略

dp [d] [x1] [x2]：从细胞（0,0）到细胞（x1，y1）和从细胞（0,0）到达细胞（x2，y2）的最大获得的钻石