题目的主要信息：

• 一个$n\ast mn*m$的表格，从左上角走到右下角的方法种数
• 每次只能走下或者右
• 不能回头

方法一：递归

具体做法：

容易想到的是，在第一步时可以选择向右或者向下，只需要当前的路径选择上加上$(n,m-1)(n,m-1)$和$(n-1,m)(n-1,m)$的矩阵路径选择即可。而$(n,m-1)(n,m-1)$与$(n-1,m)(n-1,m)$又是$(n,m)(n,m)$的子问题，可以继续递归下去。只需要用$ii$，$jj$表示当前位置，后续限制边界的向下或者向右即可。这是容易想到的方法, 下图为从$(0\mathrm{，}0)(0，0)$开始的每个子问题的递归方向，每次可以选择向下或者是向右递归，以缩短为子问题：

#include<iostream>
#include<vector>
using namespace std;

int recursion(int i, int j, int m, int n){ //递归计算方案数
    if(n == i || m == j) //到边界只有一种走法
        return 1;
    return recursion(i + 1, j, m, n) + recursion(i, j + 1, m, n); //进入子问题
}
int main(){
    int m, n;
    while(cin >> n >> m){
        cout << recursion(0, 0, m, n) << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，其中$n=max(m,n)n=max(m,n)$，递归是一个树型递归
• 空间复杂度：$O(n)O(n)$，递归栈最大深度为树的深度$nn$

方法二：动态规划

具体做法：

根据上述方法一，我们用$dp[i][j]dp[i][j]$表示到第i行j列为止的方案数，它等于到它左边的方案数加上到它上边的方案数的总和，如果是首行或者首列就等于它旁边的方案数，没有比的选择，如果是第一个就只有1种。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int m, n;
    while(cin >> n >> m){
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0)); //dp[i][j]表示到第i行j列为止的方案数
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= m; j++){
                if(i == 0 && j == 0) //最开始，一种方法
                    dp[i][j] = 1;
                else if(i == 0) //行数到顶，等于旁边列的方法
                    dp[i][j] = dp[i][j - 1];
                else if(j == 0) //列数到左边，等于旁边行的方法
                    dp[i][j] = dp[i - 1][j];
                else //等于左边加上边的方法
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        cout << dp[n][m] << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，两层遍历循环
• 空间复杂度：$O(nm)O(nm)$，dp数组的空间为$mnmn$

方法三：组合数学

具体做法：

不管怎么走，总要从左上到右下，那么要向下走$nn$次，向右走$mm$次，总共也只走$m+nm+n$次，那么方法数就是从这$m+nm+n$次中选出$mm$次向右走的方案，即$C_{m+n}^{m}C^m\_\{m+n\}$，那么最终方案数就是：

$\frac{(m+1)(m+2)(m+3)\mathrm{.}\mathrm{.}\mathrm{.}\mathrm{.}(m+n)}{n!}\backslash frac\{(m+1)(m+2)(m+3)....(m+n)\}\{n!\}$

我们只需要遍历一个$nn$计算分子分母即可计算总方案数。

#include<iostream>
using namespace std;

int main(){
    int m, n;
    while(cin >> n >> m){
        int x = 1;
        int y = 1;
        for(int i = 1; i <= n; i++){
            x *= m + i; //获取分子
            y *= i; //获取分母
        }
        cout << x / y << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一个$nn$
• 空间复杂度：$O(1)O(1)$，无额外空间