题目描述

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

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

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

算法1

(暴力枚举) $O(pow(2, (m * n)))$

时间复杂度

参考文献

C++ 代码

#include <iostream>

using namespace std;

int steps(int n, int m) {
    if (n == 0 && m == 0) {
        return 0;
    }
    if (n == 0) { 
        return 1;
    }
    if (m == 0) {
        return 1;
    }

    return steps(n - 1, m) + steps(n, m - 1);
}
/*
(2, 3) -> (0, 0)
size 3 * 4
Equation:
step(n, m) = steps(n - 1, m) + steps(n, m - 1)
1 1 1 1
1 1 1 1
1 1 1 1
*/
int main() {
    int n, m;
    cin >> n >> m;

    cout << steps(n, m) << endl;

    return 0;
}