动态规划得到最大菱形

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张,j), DP (l - 1, i, j - 1), DP (l - 1张,j - 1)) +钻石(我,我)+钻石[j, l-j]和减少钻石[j, l-j]如果我等于j。

并跳过所有不可能的地方。

总复杂度为O(N^3)

Answer 3

"你已经从0,0开始并到达最后一个单元格&然后返回0,0"

== "你已经从0开始，0到达最后一个单元格两次"

和

d: total dist

x1:第一个位置

x2: x的位置

y1: d - x1//可以提交

y2: d - x2//可以提交

dp[d][x1][x2]:从cell(0,0)到达cell (x1, y1)和cell(0,0)到达cell (x2, y2)获得的最大菱形