题目

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

思路

本来想着直接dfs加回溯，但是发现时间复杂度太大，取20的时候程序跑不出来，仔细审题后发现是高中的排列组合，组合数学O(1)可以解决。从起点到终点要走2n步，x方向和y方向分别走n步。我们只考虑一个方向，比如就是x方向，2n步肯定是要从中选取n步在x方向+1，故答案为C(2n,n);
#AC代码

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

int main()
{
    long long ans1=1;
    int j=1;
    for(int i=21;i<=40;i++)
    {
        ans1=(ans1*i)/j;
        j++;
        if(j>20)break;
    }
    cout<<ans1<<endl;
    return 0;
}