问题描述:

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

随机阅读：

**推荐内容**-

**热点内容**-
- 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