问题描述:

**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?

Ugh, I was just having fun going through my old textbooks on generating functions, and you went and changed the question again!

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

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:

```
RRUURURUUURUU
```

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

```
(8+5) choose (8)
```

Or, in general,

```
(m+n) choose (m)
```

This is simply the binomial coefficient

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

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.

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.

您可能感兴趣的文章：

- C#: Using a string variable to call and give names to other stuff
- iphone - NSString format problem
- Wcf configuration for Silverlight
- wpf - How to fix ComboBox index issue in C#
- What is the relationship between "integration testing", "continuous integration servers" and "nightly builds"?
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

- 对a，b∈R，记，函数f（x）=max{x2，2x+3}（x∈R）的最小值是________；单调递减区间为________．
- 如图是一个指甲剪的示意图，它是由三个杠杆ABC、OBD和OED组成．用它剪指甲时，属于省力杠杆的是A.ABCB.OBDC.OEDD.三个都是
- 化学兴趣小组的同学做中和反应实验时，将稀盐酸滴入氢氧化钠溶液中，看到有气泡产生，是不是拿错了药品？经检验确认没有拿错药品，而是氢氧化钠溶液变质了．【分析】氢氧化钠溶液
- problem with simple dll in c++
- 某同学从楼顶让一石块自由下落，测得石块到达地面的时间是2s，则楼房的高度为（g=10m/s2）A.20mB.40mC.45mD.60m

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial