10

对不起大家！我的错！感谢您的提醒，我发现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

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

任何人都可以给出任何提示吗？或者一个关键字如何找到答案？

4

3 回答 3

10

呃，我只是在看我关于生成函数的旧教科书很开心，你又去改变了问题！

这个问题是关于如何计算从网格（0,0）到（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)
于 2012-01-26T23:27:23.457 回答
3

这只是二项式系数

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

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

要导出公式（如果您不能只是猜测然后检查），请使用 Chris Nash 正确建议的生成函数。

于 2012-01-26T23:25:50.923 回答
2

尝试在文献中查找“生成函数”。一种方法是想象一个函数 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，也许？如果是的话，我会说最好的办法是写出一些值，猜猜它们是什么，然后证明它。

于 2012-01-26T23:14:27.937 回答