Question

两维坐标系中，仅能一次沿x或y走一步，从原点走到点的最短路径有多少条

Answer 1

每个点有两种走法，为了最短，不能回头，如果一个方向已经走完，另一个方向只有一条路可以走。
设点（x，y）
横向走1步，用a表示；纵向走一步用b表示，共走|x|a|y|b
|x|个a，|y|个b的可以区分的排列总数，就是路径数。
|x|个a是不同的，记为a1，a2，a3，...，a|x|；b1，b2，b3，..，b|y|
a1a2a3...a|x|b1b2...b|y|，不能改变各自的顺序，进行交叉排列。
设|x|，|y|中较小者为i，较大者为j，有两个方向可供选择的点有i个，走法有2i种。
从（0,0）到（x，0）或者（0，y）只有1种走法。
从（0,0）到（x，1），y方向的一步，可以在x方向的x步中间及前后任意一个位置实施，有x+1种；同理，从（0,0）到（1，y）有y+1种走法。
考虑从（0,0）到（2,3）
a1a2b1b2b3
a1b1a2b2b3，b1a1a2b2b3
a1b1b2a2b3，b1a1b2a2b3，b1b2a1a2b3
a1b1b2b3a2，b1a1b2b3a2，b1b2a1b3a2,b1b2b3a1a2
共1+2+3+4=10种。
将长方形（0,0）~（x，y）画成边长1的网格，共每行x+1条纵向路径，每列y+1条横向途径。可以用递归法求解。
F(x,y)=2+F(x-1,y)+F(x,y-1)
=2+[2+F(x-2,y)+F(x-1,y-1)]+[2+F(x-1,y-1)+F(x,y-2)]
递归到两个参数中有1个是0，结束，F（0，y）=F（x，0）=1
int F（int a，int b）
{ if （a==0 || b==0) return 1;
else return (F(a-1,b)+F(a,b-1));
}
从（0,0）到（x，y）的走法=F（abs（x），abs（y））

例如：
F（2,3）=F（1,3）+F（2,2）
=F（0,3）+F（1,2）+F（1,2）+F（2,1）
=1+F（0,2）+F（1,1）+F（0,2）+F（1,1）+F（1,1）+F（2,0）
=1+1+F（0,1）+F（1,0）+1+F（0,1）+F（1,0）+F（0,1）+F（1,0）+1
=1+1+1+1+1+1+1+1+1+1
=10