题目描述

给定一个n*m的方格阵，沿着方格的边线走，从左上角(0,0)开始，每次只能往右或者往下走一个单位距离，问走到右下角(n,m)一共有多少种不同的走法。

输入格式
共一行，包含两个整数n和m。

输出格式
共一行，包含一个整数，表示走法数量。

数据范围
$1≤n,m≤10$

样例

输入样例：

$2 3$

输出样例：

$10$

DFS

C++ 代码

#include <iostream>

using namespace std;

int n, m;
int res;

void dfs(int u, int v) //dfs(u,v)表示当前所在点
{
    if(u > n || v > m) return ;// 若当前所在点超出范围 则不记录

    if(u == n && v == m) 
    {
        res ++;
        return ;
    }//若当前所在点为M,N (即从某点通过一种方案到达了(m,n)) 则记录


    dfs(u + 1,v); // 从当前点向下走一步
    dfs(u,v + 1); // 从当前点向右走一步
}

int main()
{
    cin >> n >> m;
    dfs(0,0);
    cout << res << endl;
    return 0;
}

状态转移

C++ 代码

#include <iostream>

using namespace std;

int f(int n, int m) // f(n,m)表示到达n,m点的方案数
{
    if(m == 0 || n == 0) return 1;//在左界或上界时 只能由一个方向接受所到来的点 所以方案数为1
    return f(n - 1, m) + f(n, m - 1);// (n,m)点可由上边或者左边接收到 固加方案数即为到达上边点与左边点的和
}

int main()
{
    int n, m;
    cin >> n >> m;
    cout << f(n,m) << endl;//f(n,m)即是答案
    return 0;
}