性向拼圖

考慮在笛卡爾座標系統中的點P（N，N）。機器人必須從原點開始併到達這一點。唯一的步驟機器人可以採取有：性向拼圖

有多少不同的路徑可以使機器人採取P點？

是否有P點的最優路徑？（向上和向右步驟都會產生相同的成本）。

2011-07-16 Pritpal

您認爲如何？ –

如果正確的步驟和步驟會產生相同的成本，那麼路徑成本如何可能會有所不同？ – supercat

聽起來像面試問題...嘗試第一部分的遞歸。 – nairdaen

滾動on this Wikipedia article (Catalan number)直到你到達下面的圖片。答案就在那裏。

paths

因此，路徑總數是

formula

注：此forumal僅用於單調路徑，而不是交叉的對角線。如果你想允許穿過對角線，它需要改變一點。使用遞歸爲:)

希望它是有用的。

2011-07-16 04:54:33

這些僅僅是保持低於主對角線的路徑。 – PengOne

答覆中有一個說明。 –

是的，但我想評論仍然必要，因爲這是矯枉過正了這個問題。這個問題實際上要簡單得多。證明加泰羅尼亞語數字的公式不平凡。計算OP查找的路徑數非常簡單，不需要複雜的參數。 – PengOne

的路徑總數爲

(2n choose n)

，因爲你必須做出正確的n步驟和n了措施來結束在點(n,n)，但在其中進行的步驟的順序是無關緊要的。

所以總共有2n步驟，其中n是對的，n都漲了。以的方式選擇正確步驟的位置，其餘步驟必須加快步驟。

沒有路徑比任何其他更好的，因爲所有的路徑使用相同數量的向上和向右的步驟（包括n）。

2011-07-16 05:21:47 PengOne

它必須是（2N！）/（N！* N！）。

說明：

你必須從原點（0,0），以達到（N，N）讓我們講訴的是1個單元垂直向上，h爲1個單位horizonatally權。所有的路徑看起來是這樣 - {vvvhhhvhhhvh.... , vvhhvvhhhvvv...,........)與V和H遍佈H公司訴的數+數的長度並具有成爲

N + N = 2。

現在的路徑總數將是VS和HS的combiantion 2n個地方這將是等於

（N + N）！/（N！* N！）

因爲重複了v和h。如果還有其他單位如a或b，那麼它也會被考慮在內。我認爲這不會是一個加泰羅尼亞號碼如指出。 Rgds， Softy

2012-06-26 06:35:34 Raulp

回答