方格最短路径

走方格

基本问题：
从网格的一点走到另一点，最短路径的数目是？

A ___ ___ ___
 |___|___|___|
 |___|___|___|
              B

实际上A点到B点的最短距离就是AB间的曼哈顿距离
横向3，纵向2，最短距离为5
在所需的5步中，可以任意选两步向下，其余向右，即组合问题${5 \choose 2}$共10种路径

变形：

A ___ ___ ___
 |___|___|___|___
     |___|___|___|
                  B

和基本型的区别是，选择不再任意。如果第一步向下那么第二步必须向右
可以进行补全，只有两条路径分别经过新增的左下和右上，即${6 \choose 2}-2$共13种路径

一分也是爱~