HWOD：走方格的方案数

一、自己的解题思路

1、(0,m)和(n,0)

(0,m)表示处在棋盘的左边线，此刻能回到原点的路线只有一个，就是一路向上

(n,0)表示处在棋盘的上边线，此刻能回到原点的路线只有一个，就是一路向左

2、(1,1)

(1,1)表示只有一个方格，要想到达右下角，只有两条路，一条先下后右，一条先右后下

也就是说(1,1)的方案数等于(0,1)的方案数与(1,0)的方案数之和

3、(n,m)

有(n,m)个方格的时候，要想到达最右下角方格的右下角，无论前面怎么走，最后一定会汇聚到两条路之一，一条是最右下角方格的底边线的从左到右，另一条是最右下角方格的右边线的从上到下

所以只需要计算到达最右下角方格左下角的方案数和到达最右下角方格右上角的方案数，然后将他们加起来

而最右下角方格左下角的方案数就是(n-1,m)的方案数，最右下角方格右上角的方案数就是(n,m-1)的方案数

也就是说(n,m)的方案数等于(n-1,m)的方案数与(n,m-1)的方案数之和

至于(n-1,m)和(n,m-1)的方案数，参照上面的思路继续倒推即可

二、题目

1、描述

请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

数据范围： 1≤n,m≤8

2、输入

输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

3、输出

输出一行结果

三、自己写的代码

#include<stdio.h>
int fun(int, int);
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    printf("%d\n", fun(n, m));
    return 0;
}
int fun(int n, int m) {
    if (n == 0 || m == 0) {
        return 1;
    }
    return fun(n - 1, m) + fun(n, m - 1);
}