Question

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

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

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

数据范围
1≤n,m≤10
输入样例：
2 3
输出样例：
10

Ideas

方法一：暴搜
方法二：动态规划

Code

暴搜

#include <iostream>

using namespace std;

int n, m;

int dfs(int x, int y)
{
    int res = 0; 
    if (x == n && y == m)
    {
        res ++;
        return res;
    }
    else
    {
        if (x < n) res += dfs(x+1, y);
        if (y < m) res += dfs(x, y+1);
        return res;
    }
}

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

动态规划

#include <iostream>

const int N = 15;
using namespace std;

int f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    
    for (int i = 0; i <= n; i ++) f[i][0] = 1;
    for (int j = 0; j <= m; j ++) f[0][j] = 1;
    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i-1][j] + f[i][j-1];
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}