能力谜题

Question

考虑笛卡尔坐标系中的点P(n,n)。 一个机器人必须从原点出发并到达该点。机器人可以采取的唯一步骤是：

• 向右移动1个单位
• 向上移动1个单位。

机器人到达点P有多少不同的路径?

是否存在到达点P的最优路径?（向上和向右的步数代价相同）。

- Pritpal

---

如果向右和向上的步骤产生相同的代价，路径成本怎么可能会有所不同呢？ - supercat

听起来像是面试题...首先尝试使用递归。 - nairdaen

是的，这是一个面试问题。 - Pritpal

这里有一个类似的问题：http://projecteuler.net/index.php?section=problems&id=15 - Vili

Answer 1

路径总数为：

(2n choose n)

因为你必须向右走 n 步和向上走 n 步才能到达点 (n,n)，但是你走这些步骤的顺序无关紧要。

所以总共有 2n 步，其中 n 步向右，n 步向上。在 (2n choose n) 种方式中选择向右走的位置，其余的步骤必须向上走。

没有任何一条路径比其他路径更好，因为所有路径使用相同数量的向上和向右步骤（都是 n 步）。

- PengOne

Answer 2

请在这篇维基百科文章（卡特兰数）中滚动，直到您看到下面的图片。答案就在那里。

因此，路径的总数是

注意：此公式仅适用于单调路径，不允许穿过对角线。如果您想允许穿过对角线，则需要进行一些更改。使用递归来实现这个目的 :) 希望这对你有所帮助。

- Mihai Maruseac

---

这些仅是留在主对角线以下的路径。 - PengOne

响应中有一条注释说。 - Mihai Maruseac

是的，但我认为仍需要评论，因为这对于这个问题来说有点过头了。实际上，这个问题要简单得多。证明Catalan数列的公式并不容易。计算OP所寻找的路径数量非常简单，不需要复杂的论证。 - PengOne

那么为什么会是-1呢？这个，链接真的很好，展示了一个漂亮的离散公式。 - user166390

不确定-1是什么意思，但通过计算卡特兰数然后将它们相加的方式来做这件事情是荒谬的。直接计算路径是微不足道的。这就相当于用大锤子推进一个拇指钉。 - PengOne

我没有写添加Catalan数的代码...链接的文章只是一个解决他问题的示例。 - Mihai Maruseac

Answer 3

答案为(2n!)/(n!*n!)。

解释：

你需要从原点(0,0)到达(n,n)。 假设v代表向上1个单位，h代表向右1个单位。 所有的路径看起来像这样 - {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........)，v和h分布在v的数量+ h的数量长度上，这必须是

n + n = 2n。

现在总路径数将是2n个位置中vs和hs的组合 这将等于

(n+n)!/(n!*n!)

因为v和h是重复的。 如果有其他单位（如a或b），它也会被包括在内。 我认为这不是一个卡特兰数，正如指出的那样。 问候， 软绵绵

- Raulp