举例：对于一个2*2的二维数组，从[0,0]位置走到[1,1]位置有两种路线。（注：所有移动只能是向右‘→’方向或者向下‘↓’方向）
      对于一个3*2的二维数组，从[0,0]位置走到[2,1]位置有三种路线。（大家可以自己画一画就知道了）
      对于一个3*3的二维数组，从[0,0]位置走到[2,2]位置有六种路线。
问题：对于一个m*n的二维数组，m和n不一定相等。从[0,0]位置走到[m-1,n-1]位置有多少种路线？
      编写函数 int f(m,n) 返回路线数。

给我十分钟的时间，我只想出一个算法出来，没写出真正的程序。并且算法比较简单，面试官说我的算法效率太低。

各位有没有什么高见，说一说这个算法怎么写好

应该可以用递归的，可是我还没有学好递归，没有办法提高解决方案。

我认为C语言递归是最难学的。

这不是广搜吗?还有规律----杨辉三角
0     1     1     1      1
1     2     3     4      5
1     3     6     10    15
1     4    10    20    35
1     5    15    35    70
你要的结果就是杨辉三角的坐标的值(1.1)2 (2.1)3 (2.2)6.....

a[i][j]=a[i][j-1]+a[i-1][j]

[ 本帖最后由 Susake 于 2014-4-16 14:22 编辑 ]

f(m,1) = 1
f(1,n) = 1
f(m,n) = f(m-1,n) + f(m,n-1)

当然了，你别用递归。

--------------------------------------------

Susake 已经回答你了，我没看完回帖就回答了，sorry


[ 本帖最后由 rjsp 于 2014-4-16 08:28 编辑 ]

#include <stdio.h>

int f(int m,int n)
{
    static sum=0;
    if(0==m-1&&0==n-1) sum++;
    if(m-1>0) f(m-1,n);
    if(n-1>0) f(m,n-1);
    return sum ;
}

int main()
{
    printf("3*3的数组共有路线: %d\n",f(3,3));
    return 0;
}

我看题目中f()有返回值,在函数中用了static,所以这个方法在测试时不能反复调用,修改测试数据才可以得到答案。

原来和杨辉三角还有关系,学习了。

int main()
     {    int m,n;
          scanf("%d,%d",&m,&n);
          printf("%d*%d的数组共有路线: %d\n",m,n,f(m,n));
          return 0;
      }
测试数据。。。同学说的是什么意思？
是不是你的程序块中的main（）改成这个样子就可以用了？

动态规划