怎样求由A至B点最短的路径的数目?问题是这样的：┌┬┬┬┬┬┐B├┼┼┼┼┼┤├┼┼┼┼┼┤├┼┼┼┼┼┤└┴┴┴┴┴┘A如此组合成6x4的道路网,由A至B点最短路径只可以走「向上

Question

怎样求由A至B点最短的路径的数目?
问题是这样的：
┌┬┬┬┬┬┐B
├┼┼┼┼┼┤
├┼┼┼┼┼┤
├┼┼┼┼┼┤
└┴┴┴┴┴┘
A
如此组合成6x4的道路网,由A至B点最短路径只可以走「向上」和「向右」两个方向前往,
问共有多少条路径?

Answer 1

如果把路径一条一条的画出来——这样肯定会疯掉的
可以将每个交叉点的路径数算出来,因为只可以走「向上」和「向右」两个方向前往.
则每个点都满足这样的情况：
a b
c d
其中,b=a+d（因为只可以走「向上」和「向右」两个方向前往）
1 5 15 35 70 126 210 ( B)
1 4 10 20 35 56 84
1 3 6 10 15 21 28
1 2 3 4 5 6 7
A 1 1 1 1 1 1
由上面的数据可得出共有210条路径.