【已解决】美团面试碰到的算法题,求大佬给个思路

地图是一个二维数组,问从左上角走到右下角最长路径有多少种(最长路径就是把所有位置都走一遍,可以往上下左右4个方向走)
输入:
m, n int代表二维数组大小

输出:
最长路径的种数

样例:
输入 2 3
输出 1

题目的难点是去重

此题是leetcode980的简化版,dfs即可

#美团##笔试题目#
全部评论
dfs回溯,多加一个变量记录走的步数,看走到终点有多少种,跟leetcode980号问题类似
2 回复
分享
发布于 2020-08-27 20:37
建一个图,求最短路数量
1 回复
分享
发布于 2020-08-27 20:00
滴滴
校招火热招聘中
官网直投
dfs
1 回复
分享
发布于 2020-08-27 20:44
dp不就可以了吗,dp[i][j] 代表走到当前点有多少条路径,dp[i][j] = dp[i-1][j] + dp[i][j-1]
点赞 回复
分享
发布于 2020-08-27 19:55
这个路径不算重复走的吧,如果不能重复经过同一个位置,可以用bfs做,用一个seen记录走过的点。
点赞 回复
分享
发布于 2020-08-29 19:47
https://blog.nowcoder.net/n/d5c0b272edaa4814810a0e1f868a33f5 我写了个代码
点赞 回复
分享
发布于 2020-09-11 08:39
您好,请问这是美团一面的算法题吗?需要当场写出代码吗?
点赞 回复
分享
发布于 2020-09-14 16:00

相关推荐

1 4 评论
分享
牛客网
牛客企业服务