我正在解决一个问题,其中有一个包含 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)是肯定的,那么如果没有单元格被列入黑名单,那么我想知道内存是否有任何作用。
最佳答案
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
这是一个您之前应该见过的形状,并且知道如何直接计算每个元素。提示:您通常将其视为三角形,而不是正方形。
关于java - 冗余路径的内存,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49415519/