题目描述

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

样例

输入样例：

2 3

输出样例：

10

算法1

递推

本题的题意很清晰，直接告诉两种走法可以得到要走到 a[i][j] 只能通过 a[i-1][j] 或者 a[i][j-1], 所以 a[i][j] = a[i-1][j] + a[i][j-1]。边界也是很清晰,从第一个对角线到第一行的方案数均为1，到第一列的所有方案数均为1。(边界为0，不是1,请大家仔细思考一番)

复杂度

O(m*n) 只有两重循环，复杂度就直接相乘即可。

C++ 代码

#include <iostream>

using namespace std;

int a[20][20], n, m;

int main()
{
    cin >> n >> m;

    for (int i = 0; i <= n; i ++ )  //从第1格对角线走到第一行的所有对角线方案数均为1
        a[i][0] = 1;
    for (int j = 0; j <= m; j ++ ) //从第1格对角线走到第一列的所有对角线方案数均为1
        a[0][j] = 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            a[i][j] = a[i-1][j] + a[i][j-1]; 
            // 每个对角线只能从上边一个对角线下来，或者从左边一个对角线过来，两类走法，总方案用加法即可。

    cout << a[n][m];

    return 0;
}