冗余路径的记忆

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) 是肯定的，那么如果没有单元格被列入黑名单，那么我想知道记忆是否有任何作用。

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 开始。那太棒了。空表示 "I don't know".

用零填充数组中的每个 "blocked" 单元格。这意味着 "there is no way to get from this cell to the exit".

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

有一种方法可以从出口单元格到它自己，所以在 a[r-1][ c-1] 中填写 1。

现在算法是这样进行的：

我们被要求从单元格 (x, y) 开始的解决方案。
查询数组。如果它为 null 则递归右下邻居，并在 [x][y] 处的数组中填充这些答案的 sum
现在数组肯定已经填满了，所以returna[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

这就是我们要找的东西，所以我们完成了。

备选方案：Pre-compute数组。

我们首先像以前一样填写所有的零和出口处的一个。
现在从下往上填写最右边的一列：全部为 1，直到您到达第一个零，此时它变为全零。
现在从右到左填写最底部的一行。再次，它是所有的，直到你到达第一个零，此时它变成全零。
现在我们有足够的信息来填写 second-from-the-right 列和 second-from-the-bottom 行；你看怎么样？
如此操作直到填满整个数组。
现在所有的答案都在数组中。

示例：

第一步：

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

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

冗余路径的记忆

Memoization of redundant paths

java

memoization

dynamic-programming