寻找这个二进制递归方程的公式？f(m,n) = f(m-1,n) + f(m,n-1)

Question

对不起大家！我错了！感谢你们的提醒，我发现f(0,k) == f(k,0) == 1。这个问题是关于如何计算从网格(0,0)到(m,n)的最短路径数量。

现在我需要解决以下方程，确定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  

我记得几年前在算法课上学过解决这种二元递归方程的标准方法，但现在我就是想不起来了。

有人能给出任何提示吗？或者一个关键词如何找到答案？

- JXITC

---

你的意思是需要找到不使用递归的公式吗？还是只需要一种能够高效计算递推的算法？ - svick

你确定 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。请确认一下。 - Eugen Rieck

你正在尝试寻找闭式解吗？ - ElKamina

@EugenRieck 是的，谢谢你！！我在那里犯了一个错误。你的理解是正确的。 - JXITC

@svick 是的，我需要简化一个只包含m和n的方程，没有任何递归公式。这是一个数学问题，不是编程问题。 - JXITC

@ElKamina 闭合形式？也许是吧。谢谢 :) - JXITC

Answer 1

哎呀，我刚刚正在翻阅我的旧生成函数教科书的时候，你又修改了问题！

这个问题是关于如何计算从网格点（0,0）到（m,n）的最短路径数。

这是一个基本的组合数学问题 - 它不需要知道任何关于生成函数甚至递归关系的知识。

为了解决这个问题，可以把路径想象成一串“U”（表示向上移动）和“R”（表示向右移动）的序列。如果我们要从（0,0）移动到（5,8），就必须有5个“R”和8个“U”。这里是一个例子：

RRUURURUUURUU

在这个例子中，U和R的数量分别为8和5，不同的路径只是它们的顺序不同。因此，我们可以选择8个位置来放置U，其余的位置必须是R。因此，答案是

(8+5) choose (8)

或者，一般来说，

(m+n) choose (m)

- BlueRaja - Danny Pflughoeft

---

哇！解释得真好！爱你！ - JXITC

Answer 2

这只是二项式系数。

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

你可以通过注意到它们满足相同的递归关系来证明这一点。

如果无法猜测并验证，请使用生成函数，正如Chris Nash所建议的那样，来推导公式。

- PengOne

Answer 3

尝试在文献中查找“生成函数”。一种方法是想象一个函数P（x，y），其中x ^ m y ^ n的系数为f（m，n）。递归行（第3行）告诉您，P（x，y）- x.P（x，y）- y.P（x，y）=（1-x-y）P（x，y）应该很简单，除了那些讨厌的边缘值。然后解决P（x，y）的问题。

你确定f（k，0）= f（0，k）= k而不是1吗？如果是这样，我会建议写出一些值，猜测它们是什么，然后证明它。

- Chris Nash

---

我又犯错了。是的，它是1......天哪，我真傻。我准备重新写这个问题。 - JXITC

谢谢您的回答，我现在正在研究生成函数。 :) - JXITC

这是个好消息……原来的问题非常丑陋。修改后的问题非常漂亮。在表格中写出一些值，并将头转45度。 ;) - Chris Nash

哈哈，这清晰多了，我现在终于意识到它的基本点了。谢谢！ - JXITC

微笑 f(0,0)也是1，实际上。有且仅有一种方式不前进 :) - Chris Nash