一家公司很有意思的笔试题，看看你的逻辑能力！

一只蚂蚁要从一个4X3方格面上，从左下角走到右上角，规则是只能向右和向上且一次只能走一格，即不能向下或向左移动，
问题是给出一共有多少种走法，要列出计算公式或算法。

这只是第一问，
第二问是如果将4X3推广到N X M呢，结果是什么？写一段思路或伪代码算法

最后一问，如果不用计算机，有什么办法也能作出来？？？

ps：昨天中午吃完饭顺便面了一家，笔试这道题挺有意思的，一起来解一下！第一问自己数了下有10种走法，第二问还没有想出来。

f(n,m)=f(n-1,m)+f(n,m-1)
用二维数组记录中间值,并且f(n,m)=f(m,n),减少递归次数

public class PaGeZi {
static long[][] buf = new long[1000][1000];
static long fcount;
static long bufcount;


public static long f(int n, int m) {
fcount++;
if(n == 1 || m == 1)
return 1;
long a = buf[n-1][m], b=buf[n][m-1];
if(a == 0 && buf[m][n-1] != 0)
{
a = buf[m][n-1];
buf[n-1][m] = buf[m][n-1];
}
if(a == 0)
{
a = f(n-1, m);
buf[n-1][m] = a;
buf[m][n-1] = a;
}
else
bufcount++;

if(b == 0 && buf[m-1][n] != 0)
{
b = buf[m-1][n];
buf[n][m-1] = buf[m-1][n];
}
if(b == 0)
{
b = f(n, m-1);
buf[n][m-1] = b;
buf[m-1][n] = b;
}
else
bufcount++;

return a+b;
}

public static void clearBuf()
{
for(int i=0; i<1000; i++)
{
for(int j=0; j<1000; j++)
{
buf[i][j] = 0;
}
}
}

static void test(int n, int m)
{
clearBuf();
fcount = 0;
bufcount=0;
System.out.println("f(" + n + "," + m + ")=" + f(n,m) + "  fcount="+fcount + "  bufcount=" + bufcount);
}

/**
* @param args
*/
public static void main(String[] args) {
test(4,3);
test(10,3);
test(10,10);
test(10,20);
test(10,21);
test(10,22);
test(10,23);
test(40,8);
test(40,40);
}
}

能否在说明一点

可否解释一下思路。

应该是动态规划吧。(m,n)格子只能从其左边或者下面过来。这就是递归公式。为了解决重复计算问题，所以采用记忆法，计算过的采用查表就可以了。

高中数学公式。。组合公式C（m,k）=C(m-1,k)+C(m-1,k-1);典型的杨辉三角

3*2 ，一共要走5步。
我可以设为 左3 + 上2
当我任意给定走方格子中向上2步格子时，然后必须任选向左3个格子=C(3,5)
应该就是LZ你要的答案。。。。 

游戏里面不是有个寻址算法....

笑而不语。。。。。。。。鸭梨好大
哥哥给个网上没的综合解法：

空格 s 空格 s  空格  s 空格 s  空格  s 空格 s  空格  s 空格 s  空格  s 空格 s  空格 .........
s的个数代表需要向上的步数 
把空格=L替换为需要左走的步数

描述为把L插入到空格中，但是不重复的排列组合。

2*3   空格 s 空格 s 空格  s  空格

   A(4,1)   例如变成 ->   空格  L   空格 s  空格  s  空格   s 空格

再把另外一个L插入一共是A(5,1)中

所以一共是A(4,1)*A(5,1) 但是去掉两个L并排的状态 A(4,1)*A(5,1) / 2