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

我记得有一种标准的方法可以解决这种二进制递归方程,正如我几年前在算法类中学到的那样,但我现在还记不起来了.

任何人都可以提供任何暗示吗？或关键字如何找到答案？

Answer 1

呃,我只是通过我的旧教科书来生成函数,然后你再次改变了问题!

这个问题是关于如何计算从网格(0,0)到(m,n)的最短路径的数量.

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

要解决这个问题,想象一下路径是作为U(("up")和R("right")的序列写出来的.如果我们从(0,0)移动到(例如)(5,8),则必须有5个R和8个U. 只举一个例子:

RRUURURUUURUU

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

(8+5) choose (8)

或者,一般来说,

(m+n) choose (m)