求这个二元递推方程的公式？ f(m,n) = f(m-1,n) + f(m,n-1)
对不起，大家！我的错误！谢谢你的提醒，我发现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
我记得有一种标准方法可以解决这种二元递推方程，正如我几年前在算法课上学到的那样，但我现在不记得了。
有人能给任何提示吗？或者一个关键词如何找到答案？
SORRY GUYS! MY MISTAKE! Thanks for your reminder, I found out f(0,k) == f(k,0) == 1. This question is about how to count the number of shortest paths from grid (0,0) to (m,n).
I have to solve the following equation now, find out exactly what f(m,n) equal to.
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
for example:
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
I remember there is a standard way to solve such kinds of binary recurrence equation as I learned in my algorithm class several years ago, but I just cannot remember for now.
Could anyone give any hint? Or a keyword how to find the answer?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
呃，我刚刚在翻阅关于生成函数的旧教科书时很有趣，你又去改变了问题！
这是一个基本的组合问题 - 它不需要了解任何有关生成函数的知识，甚至不需要了解递归关系。
为了解决这个问题，想象一下路径被写成 U（代表“向上”）和 R（代表“右”）的序列。如果我们从 (0,0) 移动到 (5, 8)，则必须有 5 个 R 和 8 个 U。仅举一个例子：
在这个例子中，总是有 8 个 U 和 5 个 R；不同的路径只会以不同的顺序排列它们。所以我们可以只选择8个位置作为U，其余的必须是R。因此，答案是
或者，一般来说，
Ugh, I was just having fun going through my old textbooks on generating functions, and you went and changed the question again!
This is a basic combinatorics question - it doesn't require knowing anything about generating functions, or even recurrence relations.
To solve, imagine the paths being written out as a sequence of U's (for "up") and R's (for "right"). If we are moving from (0,0) to, say, (5, 8), there must be 5 R's and 8 U's. Just one example:
There will always be, in this example, 8 U's and 5 R's; different paths will just have them in different orders. So we can just choose 8 positions for our U's, and the rest must be R's. Thus, the answer is
Or, in general,
这只是二项式系数
。您可以通过注意它们满足相同的递推关系来证明这一点。
要导出公式（如果您不能只是猜测然后检查），请按照克里斯·纳什正确建议的那样使用生成函数。
This is simply the binomial coefficient
You can prove this by noting that they satisfy the same recurrence relation.
To derive the formula (if you couldn't just guess and then check), use generating functions as Chris Nash correctly suggests.
尝试在文献中查找“生成函数”。一种方法是想象一个函数 P(x,y)，其中 x^my^n 的系数为 f(m,n)。递归行（第 3 行）告诉您 P(x,y) - xP(x,y) - yP(x,y) = (1-xy) P(x,y) 应该非常简单，除了那些讨厌的边缘值。然后求解 P(x,y)。
您确定
f(k,0) = f(0,k) = k，而不是 1 吗？如果是的话，我认为最好的选择是写出一些值，猜测它们是什么，然后证明它。Try looking up "generating functions" in the literature. One approach would be to imagine a function P(x,y) where the coefficient of x^m y^n is f(m,n). The recurrence line (line 3) tells you that P(x,y) - x.P(x,y) - y.P(x,y) = (1-x-y) P(x,y) should be pretty simple except for those pesky edge values. Then solve for P(x,y).
Are you sure
f(k,0) = f(0,k) = k, and not 1, maybe? If it were, I'd say the best bet would be to write some values out, guess what they are, then prove it.