algorithm - 找到这个二元递归方程的公式？ f(m,n) = f(m-1,n) + f(m,n-1)

Question

抱歉，伙计们!我的错!谢谢提醒，我发现f(0,k) == f(k,0) == 1 这道题是关于如何统计从grid(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  

我记得几年前我在算法课上学过，有一种标准的方法可以求解这类二元递归方程，但我现在想不起来了。

谁能给点提示？或者一个关键字如何找到答案？

Answer 1

呃，我只是在愉快地阅读我的关于生成函数的旧教科书，而你又去改变了问题!

This question is about how to count the number of shortest path from grid (0,0) to (m,n).

这是一个基本的组合问题 - 它不需要了解有关生成函数甚至递推关系的任何知识。

要解决这个问题，请将路径想象为一系列 U(表示“向上”)和 R(表示“右”)。如果我们从 (0,0) 移动到，比方说，(5, 8)，则必须有 5 个 R 和 8 个 U。举个例子:

RRUURURUUURUU

在这个例子中，总会有 8 个 U 和 5 个 R；不同的路径只会让它们以不同的顺序排列。所以我们可以只为我们的U选择8个位置，其余的必须是R。因此，答案是

(8+5) choose (8)

或者，一般来说，

(m+n) choose (m)