查找NxN网格中所有路径的算法

想象一下，一个机器人坐在NxN网格的左上角。机器人只能在两个方向上移动：向右和向下。机器人有多少条可能的路径？

我可以在Google上找到解决此问题的方法，但是我对这些解释并不十分清楚。我试图清楚地了解有关如何解决此问题并在Java中实现的逻辑。任何帮助表示赞赏。

更新：这是一个面试问题。现在，我试图到达右下角并打印可能的路径。

我认为您的问题中没有障碍的迹象，因此我们可以假设没有障碍。

请注意，对于n + 1 x n + 1的网格，机器人需要精确地执行2n步骤才能到达右下角。因此，它只能采取2n行动。

[找到右下角的所有路径]

机器人可以精确地确定路径：它只需要选择正确的移动方式，其余的向下移动即可。

。1表示向右移动，0表示向下移动。choose(n,2n)=

(2n)!/(n!*n!)``2n``n

2n``n

首先选择的长度。为此，请遍历所有可能性：0 <= i <= 2n，i路径的长度在哪里。这条道路上有max(0,i-n) <= j

<= min(i,n)正确的步骤。

要生成所有可能性，请实现以下伪代码：

for each i in [0,2n]:
  for each j in [max(0,i-n),min(i,n)]:
    print all binary vectors of size i with exactly j bits set to 1

打印所有大小为i且j位设置为1的二进制矢量可能在计算上很昂贵。这是可以预期的，因为存在成倍的解决方案。

对于case i=2n，您将得到j in [n,n]预期的效果（上述更简单的情况）。