algorithm - 机器人在网格算法中移动的可能路径和时间复杂度 ?

Question

我无法理解以下路径数为 (x+y)!/x!y! ..我知道它来自从 X+Y 项目的路径中选择 X 项目，但为什么不选择 x 项目而不是 x+y + 选择 y 项目而不是 x+y ？为什么它必须只有 x ？

机器人位于 amxn 网格的左上角（在下图中标记为“开始”）。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角（在下图中标记为“完成”）。有多少种可能的路径？

1. 所有这些路径都是独一无二的吗？
2. 我如何确定？
3. 回溯算法的时间复杂度是多少？

Answer 1

这有点基于Mukul Joshi 的回答，但希望更清楚一点。

要从0,0到x,y，您需要准确地向右移动x时间并准确地向下移动y。

让每个向右运动由 a 表示，0向下运动由 a 表示1。

让一串0s 和s 表示从到1的路径。该路径将包含s 和s。0,0x,yx 0y 1

现在我们要计算所有这些字符串。这相当于计算任何包含x 0s 和y 1s 的字符串的排列次数。这个字符串是一个多重集（每个元素可以出现多次），因此我们想要一个多重集排列，它可以计算为n!/(m1!m2!...mk!)wheren是总字符数，k是唯一字符的数量，是唯一的mi次数i字符重复。由于总共有x+y字符，并且0是重复x次数和1重复y次数，我们得到(x+y)!/x!y!。

时间复杂度：

回溯/蛮力的时间复杂度将涉及必须探索所有这些路径。把它想象成一棵树，有(x+y)!/x!y!叶子。我可能是错的，但我认为具有分支因子的树中的节点数> 1可以表示为叶子数的大 O，因此我们最终得到O((x+y)!/x!y!)节点，因此具有相同的时间复杂度。

Answer 2

好的，我给你一个解决这个问题的方法，这样你就有更好的时间去解决它。
首先，让我们决定一个解决算法。我们将计算每个细胞从它到达终点的所有可能路径。该算法将检查单元格并在那里写入右侧和底部单元格的总和。我们这样做是因为机器人可以向下移动并遵循任何底部路径或向右移动并遵循任何右侧路径，从而增加不同路径的总数。对我来说，证明这些路径的多样性是很明显的。如果你愿意，我可以在评论中做到。
对于最右边的底部单元格（完成），单元格的初始值将是 1，因为只有一种方法可以从该单元格到达那里（根本不移动）。如果单元格不存在（例如，将底部单元格作为最底部的单元格），它将具有 0 值。
一个一个地构建单元格值将产生一个帕斯卡三角形，其值(x + y)! / x! / y!位于 (x, y) 单元格中，其中 x 是距终点的 Ox 距离，y 是 Oy 1。

谈到复杂性，我们将x * y在网格单元上进行迭代，每次迭代都是一个常数时间。如果您不想使用回溯算法，您可以使用上面提到的公式并使用 O(x + y) 而不是 O(x * y)

Answer 3

那么这里是解释。

无论如何，要到达目的地，路径必须有 m 行和 n 列。

假设您用 1 表示行，用 0 表示列。您的路径是一串 m+n 个字符。但它只能有 m 个 1 和 n 个 0。

如果您有 m+n 个不同的字符，则排列数将为 (m+n)！但是当您有重复字符时，它将是 (m+n)!/m!n! 参考这个

当然，这将是独一无二的。测试它的 4*3 网格，你可以看到它。

Answer 4

您没有添加“我可以通过多少种方式分配我的 X 招式？” 到“我有多少种方式可以分配我的 Y 移动？” 有两个原因：

1. X招式和Y招式的分布不是独立的。对于 X 动作的每种配置，Y 动作只有 1 种可能的配置。
2. 如果它们是独立的，您不会将它们相加，而是将它们相乘。例如，如果我有 X 种不同颜色的衬衫和 Y 种不同颜色的裤子，那么衬衫和裤子就有 X * Y 种不同的组合。

请注意，对于#1，X 没有什么特别之处——我可以很容易地选择 Y 并说：“Y 移动和 X 移动的分布不是独立的。对于 Y 移动的每个配置，X 仅有 1 种可能的配置动。” 这就是为什么，正如其他人所指出的那样，计算分配 Y 动作的方式数量与计算分配 X 动作的方式数量相同的结果。