java - 冗余路径的内存

Question

我正在解决一个问题，其中有一个包含 r 行和 c 列的网格。我们从左上角的单元格开始，到右下角的单元格结束。限制是我们一次只能向下或向右移动一个单元格。此外，某些小区可能会被列入黑名单。问题是找出总数。我们可以从源到目标的方法。

这是我的解决方案，它很简单，但运行时间呈指数级:

int count(boolean[][] array, int r, int c)
{
    if ((r < 0 || c < 0) || !array[r][c]) return 0;
    if (r == 0 && c == 0) return 1;
    return count(array, r - 1, c) + count(array, r, c - 1);
}

我遇到的问题是在记住这一点时。

1. 内存可以使该解决方案更加高效吗？
2. 如果是这样，那么我无法将失败路径中的所有单元格列入黑名单，因为可能存在通过这些单元格的其他路径可能导致目标。所以我很困惑，我应该在这里缓存什么，以及在哪里添加额外的检查以避免检查我已经走过的路径。
3. 如果(1)是肯定的，那么如果没有单元格被列入黑名单，那么我想知道内存是否有任何作用。

Answer 1

Can memoization make this solution be made more efficient?

是的!

If so, then I cannot blacklist all the cells that are in a path that fails because there might be other paths through those cells which may lead to target.

正确。

So I'm confused so as to what I should cache here and where do I add the additional check to avoid checking on paths I have already gone through.

这就是你要做的。

创建一个可空整数的 r x c 二维数组，我们称之为 a 。数组的含义是“a[x][y]给出从(x,y)到(r-1,c-1)的路径数”——假设(r-1,c-1)是“exit”我们试图到达的单元格。

数组将从每个元素为空开始。那太棒了。 Null 表示“我不知道”。

用零填充数组中的每个“阻塞”单元格。这意味着“没有办法从这个牢房到达导出”。

如果a[r-1][c-1]为零，则导出被堵塞，我们就完成了。每个查询的答案都是零，因为没有办法到达导出。我们假设导出单元没有被阻塞。

有一种方法可以从导出单元到达其自身，因此填写 a[r-1][ c-1]与 1.

现在算法如下:

• 我们被要求提供从单元格 (x, y) 开始的解决方案.
• 查阅数组。如果为空，则递归向右和向下的邻居，并在 [x][y] 处填充数组。这些答案的总和
• 现在数组肯定已经填满了，所以返回a[x][y] 。

让我们举个例子。假设我们有

n  n  n
n  n  0
n  n  1

我们被要求提供 (0, 1) 的解。我们没有解决办法。因此我们尝试寻找 (1, 1) 和 (0, 2) 的解。

我们没有 (1, 1) 的解。所以我们必须得到 (1, 2) 和 (2, 1) 的解。

(1, 2) 我们已经得到了。是 0。

(2, 1) 我们没有，但 (2, 2) 我们有，而且这是唯一的邻居。 (2, 2) 为 1，所以我们填写 (2, 1):

n  n  n
n  n  0
n  1  1

现在我们有足够的信息来填写 (1, 1):

n  n  n
n  1  0
n  1  1

我们还没有完成 (0, 2)。它有一个为零的邻居，因此:

n  n  0
n  1  0
n  1  1

现在我们可以填写 (0, 1)

n  1  0
n  1  0
n  1  1

这就是我们正在寻找的内容，所以我们已经完成了。

替代解决方案:预先计算数组。

• 我们首先像以前一样填写所有零和导出处的一。
• 现在从下往上填写最右边的一列:全是 1，直到到达第一个零，此时它就变成全 0。
• 现在从右到左填写最底行。同样，它都是全一，直到你到达第一个零，此时它就变成全零。
• 现在我们有足够的信息来填写右数第二列和倒数第二行；你知道怎么做吗？
• 以此类推，直到填满整个数组。
• 现在所有答案都在数组中。

示例:

第一步:

n  n  n
n  n  0
n  n  1

填写外侧的行和列:

n  n  0
n  n  0
1  1  1

填写下一行和下一列:

n  1  0
2  1  0
1  1  1

最后一个:

3  1  0
2  1  0
1  1  1

我们就完成了；整个问题就解决了。

if there were no cells blacklisted, then I was wondering if the memoization would have served any purpose at all.

如果没有单元格被列入黑名单，则数组如下所示:

20 10  4  1
10  6  3  1
 4  3  2  1
 1  1  1  1

这是一个您之前应该见过的形状，并且知道如何直接计算每个元素。提示:您通常将其视为三角形，而不是正方形。