找到这个二元递推方程的公式？ 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

回答