题目15：在20*20的网格中，从左上角通往右下角的路径一共有多少？

欧拉计划

题目15：在20*20的网格中，从左上角通往右下角的路径一共有多少？

Lattice paths

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?

题目翻译：

从一个 2×2 网格的左上角开始，只能向右和向下移动，

有 6 条（不允许往回走）通往右下角的路径。



对于 20×20 的网格，这样的路径一共有多少条？


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

zhangjinxuan

and only being able to move to the right and down

只能向右向下走呗，这个关键的信息居然没有翻译

那么，这就很简单了

第 i 行 j 列的路径总数，等于 第 i-1 行 j 列的路径总数 + 第 i 行 j-1 列的路径总数。

第 1 行 1 列的路径总数为 1。

#include <bits/stdc++.h>
using namespace std;

long long f[21][21];
const int n = 20;

int main() {
        f[1][1] = 1;
        for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                        if (i == 1 && j == 1) continue;
                        f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
        }
        printf("%lld\n", f[n][n]);
        return 0;
}

得出答案：35345263800。

不二如是

此答案来自gpt，你们看出错了吧

这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。

对于一个m×n的网格,总共有(m+n)!/(m!*n!)条路径。

通过python实现:

from math import factorial

def path(m, n):  
    return factorial(m + n) / (factorial(m) * factorial(n))

print(path(20, 20))
# 24164578454568703130937340141

详细解释:

• factorial() 函数用于计算阶乘。
• m+n 表示可以移动的步数,有(m+n)个选择。
• m! 和 n! 分别表示排除掉上下移动和左右移动。
  

因此总共有(m+n)!/(m!*n!)条路径。

歌者文明清理员

不二如是 发表于 2023-7-8 09:44
这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。

Chat***？

zhangjinxuan

不二如是 发表于 2023-7-8 09:44
这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。

wq，答案居然不一样

zhangjinxuan

杨 辉 三 角

小甲鱼

zhangjinxuan 发表于 2023-7-9 10:01
杨 辉 三 角

C(40, 20)

zhangjinxuan

小甲鱼 发表于 2023-7-9 23:49
C(40, 20)

zhangjinxuan

不二如是 发表于 2023-7-8 09:44
此答案来自gpt，你们看出错了吧

这是一个组合问题。

嗯，是gpt啊，这就不奇怪了，这就不奇怪了

（zhangjinxuan撤销了一碗饭）

clollipops

C(40, 20) = 137846528820

忘川hd

好好学习

鸡你实在太没

clollipops，哇！那么好的解析

MoistenLe

先打个卡  现在挑战不了

一只菜狗

佬们，递归一下

zhuyanan

这个题目有点复杂呀  好难呐

Tiamsy

慢慢来

549246531

137,846,528,820

爱吃梨的猩猩

太有意思了吧，有用有用

a18907596

一进来感觉进入了太极八卦阵，，，，，可惜我这不好好学习的看不懂。。尴尬

shane9611

学习学习～