在座標2D平面上從點1移動到點2的方法數

Question

我遇到了一個問題，在這個問題中，要求找到在2D座標系中從點1到點2達到的唯一方法的數量，縱座標。

注意：這可假定爲不失一般性，即x1 < x2和y1 < y2。

此外，動作受到以下方式的限制。一個人只能向右或向上移動。意味着如果xa < xb和ya < yb有效的移動是從(xa, ya)到(xb, yb)。

在數學上，這可以通過([(x2-x1)+(y2-y1)]!)/[(x2-x1)!] * [(y2-y1)!]找到。我也想過代碼。

我有我用動態編程進行編碼的方法，我的方法需要大約O([max(x2,y2)]^2)時間和Theta(x2 * y2)，我可以用上或下三角矩陣來管理。

你能想到其他一些方法，其中運行時間比這少嗎？我正在考慮最小運行時間爲O(max(x2,y2))的遞歸解決方案。

Answer 1

我終於成功地撰寫了文章來詳細描述這個問題並完成了答案。這裏是相同的鏈接。 http://techieme.in/dynamic-programming-distinct-paths-between-two-points/

Answer 2

一個簡單高效的解決方案是數學方法。

讓x2-x1 = n和y2-y1 = m。
你需要採取正確的步驟n步驟，並m步驟，所有剩下來確定是他們的順序。

這可以被建模爲二進制向量的數量與n+m元素設置爲1
因此究竟n元素的可能性總數爲chose(n,n+m) = (n+m)!/(n! * m!)，這是你得到了什麼。

鑑於數學答案既經過驗證，計算速度也更快 - 我沒有理由對這些限制使用不同的解決方案。

如果您急於在這裏使用遞歸，recursive formula for binomial coefficient可能會很適合這裏。

編輯： 您可能正在尋找multiplicative formula來計算它。

Answer 3

要計算答案，你可以用這個公式：

(n+m)!/(n!m!)=(n+1)*(n+2)/2*(n+3)/3*…*(n+m)/m

所以僞代碼是：

let foo(n,m) = 
    ans=1; 
    for i = 1 to m do 
    ans = ans*(n+i)/i; 
    done; 
    ans 

乘法和除法的順序很重要，如果你修改即使結果不是很大，也可能發生溢出。