我要招人

去企业版

首页 > 试题广场 >

假设下图中每个正方形的边长为1，则从A到Z的最短路径条数为?

[单选题]

```
11
```
```
12
```
```
13
```
```
14
```

查看正确选项

钜子墨苍离

动态规划求解：

每个顶点对应的对端路径数目如下：

1 1 1 1

1 2 3 4 4

2 5 9 13

其中递推关系为f（x，y）=f（x-1,y）+f（x，y-1）。即每一个点的值=左边点值+右边点值

类似的题型是棋盘寻宝

发表于 2015-08-28 17:15:23 回复(5)

更多回答

Coding-robot

C(2,6)-2

发表于 2015-11-11 11:12:45 回复(5)

★☆

选C 从向下走的列数来考虑，第一层有4根往下走的竖，第二层也有4根，那么总共有路径4*4=16，再减去不是最短的路径，第一条是：第一层的第3竖->第二层的第1竖；第二条是：第一层的第4竖->第二层的第1竖；第三条是：第一层的第4竖->第二层的第2竖；所以最短路径条数为16-3=13

发表于 2016-07-26 12:13:23 回复(0)

剑已凌乱

简单点：只需考虑竖着的，一共两层，上面4，下面4.上面那层从第一根下了，那么剩下那层有4种走法，从第二根下来，也有4种，从第三根下来3种，第四根2种

发表于 2016-10-27 23:29:43 回复(0)

一只肉咕咕

如果是完整2*4方格子，总共6步，不是往右就是往下，就看往下的是哪两步，所以是C(2,6)种，

再减去边路的两种就是C(2,6)-2种呗~~

编辑于 2017-10-18 22:03:05 回复(1)

linko解万

发表于 2014-12-29 10:10:56 回复(0)

产品白客

类似排列组合问题：（如果是完整的4*2表格那走法就是）C6取2，但由于少了边角的两个矩形，减去两种走法，即15-2=13种走法

发表于 2020-02-22 08:13:06 回复(0)

Violord

因为都是正方形，可以不用考虑具体长度，直接看做三个岛，中间的岛向两边各有四座桥，桥的位置还按这个图来。则过程简化成：

从岛1左边过四座桥中任意一桥到岛2，然后从岛2过四座桥中任意一桥到岛3右边。

---------------------------------------

| 岛1 |

--------------------------------------

|桥| |桥| |桥| |桥|

---------------------------------------

| 岛2 |

--------------------------------------

|桥| |桥| |桥| |桥|

---------------------------------------

| 岛3 |

--------------------------------------

想要路程最短，则从岛1过桥至岛2后，不走位置比来时的桥靠左的桥就行了。所以，对应从岛1至岛2从左到右的四座桥，分别有4，4，3，2种过桥方法，因此有4+4+3+2=13种走法。

发表于 2019-10-16 16:58:13 回复(0)

666的佩奇爸爸

答案：C。

本题中，假设为上图的左下角与右上角补充两个小正方形，那么此时从点A到点Z需要横着走4格，竖着走2格，此时最短路径有C(6,2)或C(6,4)种情况，即(6*5)/2=15种情况。当然，最终结果不是15，由于整个图形补充了两个缺口，所以，必须在15的基础上减去2，最终结果为15-2 = 13。因此，选项C正确。

发表于 2018-07-17 20:16:19 回复(0)

无双.com

这里最短路径就是4横2竖，所以只能往右和往下走。

直接考虑竖的选择，发现需满足

1.所需竖条数为2，并且上下各一根，C(4,1)*C(4,1)=16种情况

2.上面的竖必须不超过下面的竖，这样横才能连接的上。简单比较一共有3种情况

16-3=13 选C

发表于 2022-02-04 20:30:56 回复(0)

雀巢崔崔鲨

你小子不能斜着走啊

编辑于 2024-03-11 14:45:34 回复(0)

牛客390412555号

完全搞不懂，什么是动态规划啊，大学没学啊

发表于 2022-06-05 20:37:35 回复(0)

牛客748519424号

保证路径一直是向右向下，在每个节点都选择向右向下

发表于 2021-07-21 21:56:52 回复(0)

视觉～刻录Ra

动态规划求解：每个顶点对应的对端路径数目如下： 1 1 1 1 1 2 3 4 4 2 5 9 13 其中递推关系为f（x，y）=f（x-1,y）+f（x，y-1）。即每一个点的值=左边点值+右边点值类似的题型是棋盘寻宝

发表于 2019-07-25 22:03:48 回复(0)

许愿论文答辩顺利通过顺利毕业🙏

f（x，y）=f（x-1,y）+f（x，y-1）

发表于 2019-04-15 16:36:10 回复(0)

Rachy

动态规划求解：

每个顶点对应的对端路径数目如下：

1 1 1 1

1 2 3 4 4

2 5 9 13

其中递推关系为f（x，y）=f（x-1,y）+f（x，y-1）。即每一个点的值=左边点值+右边点值

类似的题型是棋盘寻宝

发表于 2017-04-27 20:05:44 回复(0)

kpz

有5种可能走向：→↓→↓*3 + →↓→*3 + →↓→↓→*3 + ↓→↓*1 + ↓→↓→*3，共13种

发表于 2015-04-02 16:59:46 回复(0)

提交观点

问题信息

数学运算

上传者：乐芝木糖醇

难度：

17条回答 563收藏 5200浏览

假设下图中每个正方形的边长为1，则从A到Z的最短路径条数为?

问题信息

热门推荐

相关试题