牛客 拜访

原题链接:

https://www.nowcoder.com/practice/12cbdcdf5d1e4059b6ddd420de6342b6?tpId=49&tqId=29283&tPage=1&rp=1&ru=/ta/2016test&qru=/ta/2016test/question-ranking

题目:

现在有一个城市销售经理,需要从公司出发,去拜访市内的商家,已知他的位置以及商家的位置,但是由于城市道路交通的原因,他只能在左右中选择一个方向,在上下中选择一个方向,现在问他有多少种方案到达商家地址。

给定一个地图map及它的长宽nm,其中1代表经理位置,2代表商家位置,-1代表不能经过的地区,0代表可以经过的地区,请返回方案数,保证一定存在合法路径。保证矩阵的长宽都小于等于10。

测试样例:
[[0,1,0],[2,0,0]],2,3

返回:2

这是美团的一道题,显然用动态规划非常好求解,关键是要找到动态规划的迭代公式。



leetcode上面有一道非常类似的题目,好像是描述的一个机器人要到达一个地方应该怎么走,但是只需要考虑一个方向,并且不需要考虑一些地方无法到达的情况,微简单了一些。

共有 0 条评论

Top