请编写一个函数(允许增加子函数),计算n x m的棋盘格子(n为横向的格子数,m为竖向的格子数)沿着各自边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。———牛客
对于n*m的棋盘,可分为以下两种情况:
1.当n == 1或 m == 1时,共有n+m种走法(不为1的加1种);
2.当n、m都大于1时,那么最终走到右下角只有两条路径:
(1)从[n-1, m]到右下角;
(2)从[n, m-1]到右下角。
假设从左上角走到[n, m]位置有f(n, m)种走法,则:n*m的棋盘从左上角到右下角共有f(n-1, m) + f(n, m-1)种走法。
因此,我们可以使用递归解决上述问题,退出条件为1.
实现:
1 int func(int n, int m)2 {3 if(n == 1 || m == 1)4 return n+m;5 else6 return func(n-1, m) + func(n, m-1);7 }