找到這個二元遞推方程的公式？ f（m，n）= f（m-1，n）+ f（m，n-1）

SORRY GUYS！我的錯！感謝您的提醒，我發現f（0，k）== f（k，0）== 1.這個問題是關於如何計算從網格（0,0）到（m，n）的最短路徑數）。找到這個二元遞推方程的公式？ f（m，n）= f（m-1，n）+ f（m，n-1）

我現在必須解出下面的公式，準確地找出f（m，n）等於什麼。

1) f(m,n) = 0 : when (m,n) = (0,0) 
**2) f(m,n) = 1 : when f(0,k) or f(k,0)** 
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else

例如：

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3

我記得有我在我的算法類幾年以前就學會了解決這種類型的二進制遞推方程的標準方法，但我不記得現在。

任何人都可以提供任何提示嗎？或者一個關鍵詞如何找到答案？

2012-01-26 JXITC

你的意思是，你需要找到一種不使用遞歸的公式？或者只是一種有效計算循環的算法？ – svick 2012-01-26 23:03:24

你確定f（2,1）= 3嗎？我讀取f（2,1）= f（1,1）+ f（2,0）=（f（0,1）+ f（1,0））+ f（2,0）=（1 + 1 ）+ 2 = 2 + 2 = 4 – 2012-01-26 23:03:42

您正在努力尋找封閉的表單解決方案嗎？ – ElKamina 2012-01-26 23:05:44

呃，我只是開始閱讀我的舊教科書中關於生成函數的內容，然後你又去改變了這個問題！

這個問題是關於如何計算從網格（0,0）到（m，n）的最短路徑的數量。

這是一個基本的組合問題 - 它不需要知道任何關於生成函數，甚至是重複關係的任何事情。

爲了解決這個問題，設想路徑被寫成一系列U（用於「up」）和R（用於「right」）。如果我們從（0,0）移動到例如（5,8），那麼必須有5個R和8個U。只是一個例子：

RRUURURUUURUU

在這個例子中，總是會有8個U和5個R;不同的路徑會以不同的順序擁有它們。所以我們可以爲我們的U選擇8個位置，其餘的必須是R's。因此，答案是

(8+5) choose (8)

或者說，在一般情況下，

(m+n) choose (m)

2012-01-26 23:27:23

哇！很好的解釋！愛你！ – JXITC 2012-01-26 23:31:00

試着在文獻中查找「生成函數」。一種方法是設想其中x^m y^n的係數是f（m，n）的函數P（x，y）。重複行（第3行）告訴你，P（x，y） - xP（x，y） - yP（x，y）=（1-xy）P邊緣值。然後求解P（x，y）。

你確定f(k,0) = f(0,k) = k，而不是1，也許？如果是這樣，我會說最好的辦法就是寫出一些數值，猜測它們是什麼，然後證明它。

2012-01-26 23:14:27

= =！我又犯了一個錯誤。是的，它是1 ...... OMG，我多麼傻。我即將重寫這個問題。 – JXITC 2012-01-26 23:17:11

並感謝您的回答，我正在尋找現在生成的功能。 :) – JXITC 2012-01-26 23:21:17

這是個好消息......原來的問題非常難看。修改後的版本非常漂亮。在表格中寫出一些值，然後將頭轉45度。 ;） – 2012-01-26 23:25:47

這簡直是二項式係數

f(m,n) = (m+n choose m) = (m+n choose n)

您可以通過注意它們滿足相同的遞推關係證明了這一點。

要推導出公式（如果你不能猜測然後檢查），請使用Chris Nash正確建議的生成函數。

2012-01-26 23:25:50 PengOne

非常感謝你:) – JXITC 2012-01-26 23:38:02

回答