一道⁺ / edao.plus

#10064

最短路径·标数法

计数五年级 #标数法 #组合

题目

在由 4 行 5 列格点组成的方格网中（点共 4 × 5 = 20 个），小明要从左下角 A 走到右上角 B，每一步只能沿着格子线向右走一格或向上走一格。

问从 A 到 B 一共有多少条不同的最短路径？

解法

按从左下向右上依次相加填数，填到右上角 B 得 35 条最短路径。
1410203513610151234511111

方法

标数法在网格 / 图的每个交点写上“从起点走到这里的路径数”，从起点逐格推到终点。组合从 n 个不同元素中无序地取 k 个的方法数：C(n, k) = n! ÷ (k! × (n − k)!) = A(n, k) ÷ k!。

练一练

在 4 行 4 列格点组成的方格网中（水平方向 3 格，竖直方向 3 格），从左下角 A 走到右上角 B，每步只能向右或向上。共有多少条最短路径？

相关题目

#10035 排列组合·选人组队

组合 / 排列 / 乘法原理

计数五年级

#10038 几何计数·数线段

组合 / 加法原理

计数三年级