【题解】方格走法

题目描述

有一个X*Y的网格，小团要在此网格上从左上角到右下角，只能走格点且只能向右或向下走。请设计一个算法，计算小团有多少种走法。给定两个正整数int x,int y，请返回小团的走法数目。

输入描述

输入包括一行，空格隔开的两个正整数x和y，取值范围[1,10]。

输出描述

输出一行，表示走法的数目

示例1
输入

3 2

输出

10

因为只能往右或者往下走，所以对于每一个格点来说，走到它的走法数是走到它上边格点的方法数和走到它左边格点的方法数之和。
然后可以发现，第一行和第一列的格点，一定是只有一种方法可以到达的，如图中红色格点所示。

这样的话先对这些格点进行初始化，然后从第二行第二列开始遍历剩下的格点，更新数值就好了~
记 表示走到第 行第 列格点有多少方法，
更新的方式是
更新结束之后， 就是答案了

#include <iostream>

using namespace std;

int main()
{
    int x,y;
    cin >> x >> y;
    x++;y++;//题目中给出的是格子数，而我们要算的是格点，所以需要+1
    int arr[20][20];//数组比范围大一些，防止越界
    for(int i = 1 ; i <= x ; i++)//初始化第一列
    {
        arr[i][1] = 1;
    }
    for(int i = 1 ; i <= y ; i++)//初始化第一行
    {
        arr[1][i] = 1;
    }
    for(int i = 2 ; i <= x ; i++)//更新
    {
        for(int j = 2 ; j <= y ; j++)
        {
            arr[i][j] = arr[i-1][j]+arr[i][j-1];
        }
    }
    cout<<arr[x][y]<<endl;
    return 0;
}