题意理解

格子是有m行n列，沿着格子的边，从左上角走到右下角，每次只能向右或者向下走。我们是从一个点到另一个点，不是从格子到格子。

方法一

使用递推的方法。我们用数对(i,j)表示点的位置。每一个点只可能从它的左边或者上面走一步过来，所以到点(i,j)的走法总数等于到达点(i-1,j)和(i,j-1)的走法总数之和。注意初始化，到第0行和第0列上每个点的走法都为1种。

示意图如下：

具体代码如下：

#include<iostream>

using namespace std;

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int path[10][10];
        //初始化矩阵
        for (int i=0;i<=n;i++)
        {
            path[0][i] = 1;
        }
        for (int i=0;i<=m;i++)
        {
            path[i][0] = 1;
        }
        //递推过程
        for (int i=1;i<=m;i++)
            for (int j=1;j<=n;j++)
                path[i][j] = path[i-1][j] + path[i][j-1];
        cout<<path[m][n]<<endl;
    }
    return 0;
}

时间复杂度： O(NM)。递推过程是一个双重for循环。
空间复杂度： O(NM)。开辟了path二维数组，当然在本题中由于数据范围问题，数组大小给定了常数。

方法二

由于只能向右或者向下走，则走的次数是一定的，即必然要向右走n步，向下走m步。那么一共n+m步中，哪n步向右走就决定了所有可能的走法。这就转化为了一个组合问题，我们求出C(n+m,n)即可。注意求组合数的时候先约分。

具体代码如下：

#include<iostream>

using namespace std;

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        int c = n + m;
        int ans = 1;
        //求组合数
        for (int i=n+1;i<=c;i++)
        {
            ans = ans * i;
        }
        for (int i=1;i<=m;i++)
        {
            ans = ans / i;
        }
        cout<<ans<<endl;
    }
    return 0;
}

时间复杂度： O(N)。准确地讲应该是max(n,m)，可以看到是两个for循环。
空间复杂度： O(1)。没有开辟新空间。