首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
牛客769570832号
武汉理工大学 Java
发布于湖北
关注
已关注
取消关注
@蘑菇睡不着:
题解 | #走网格#
描述一个nxm的网格中,起点在(1,1),终点在(n,m),网格中有一块不能走的矩形区域,左下坐标为(x0,y0),右上坐标为(x1,y1),求从起点到终点的路径条数。 示例1 输入:4,4,2,2,3,3返回值:2说明:只有两条可达路径思路 这道题是求从起点到一个格子的所有路径。大家看上面的红点所在的格子,想要到红点所在的格子有两条路:一是:从红点左侧的格子过来;二是:从红点下侧的格子过来;然后我想要知道 红点 左侧格子有几条路径,也是用同样的方法。这样看来,我想求某个格子的路径数量应该是如下公式: dp[m][n] = dp[m - 1][n] + dp[m][n - 1]; dp[m][n]: 某个格子的坐标; dp[m - 1][n]:是格子左侧的格子路径数量; dp[m][n - 1]:是格子下侧的格子路径数量; 这么就是动态规划的 状态转移方程。动态规划除了状态转移方程还有一个重要的元素,那就是 初始值。这道题的初始值很好确定,dp[1][1] = 1。就是起点位置默认是一条路径。 AC代码 public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) { // write code hereå if (m < 1 || n < 1) { return 0; } // 初始化dp数组 int[][] dp = new int[n + 1][m + 1];å // 设置默认值 dp[1][1] = 1; // 开始遍历所有格子 for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (i == 1 && j == 1) { continue; } // 当遇到不能走的区域 跳过 if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue; // 每个格子的路径条数 = 左侧数量 + 下侧数量 dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%1000000007; } } return dp[n][m]; } 时间复杂度:O(m*n), m 和 n 分别是长宽,因为所有的格子都要遍历到。 空间复杂度:O(m*n),要将这些格子存储到 dp[m][n],二维数组中。 最后 更多的刷题已经知识,大家可以来我的博客看一看
点赞 0
评论 0
全部评论
推荐
最新
楼层
暂无评论,快来抢首评~
相关推荐
07-25 13:44
华东理工大学 Java
海尔提前批简历挂
竟然连简历都过不了
投递海尔等公司7个岗位
点赞
评论
收藏
分享
今天 17:28
南京航空航天大学 产品经理
感觉mentor经常答非所问,怎么办?
感觉我的mt经常答非所问,和他讲话恰如对牛弹琴,鸡同鸭讲。每次问完我都是黑人问号??但介于实习生的身份也不敢再多问,就只能问其他同事。后来我实在没忍住和其他实习生吐槽了这事,他们也觉得认同我的想法。如果因为他我选择跑路,感觉又不值得,毕竟是一个知名大厂,如果不走,和他工作我就要难受至少3个月……牛友们,咋办呀!
点赞
评论
收藏
分享
07-03 16:13
嘉应学院 Python
请问这个是骗子吗😂
xiaolihuam...:
很明显骗子,如果是hr直接约你面试了,哪用得着内推,如果是员工的话,你得多优秀,一线员工直接加你微信,
点赞
评论
收藏
分享
07-29 14:02
湖北大学 后端
简历要改吗?
最近投了好多家都是已读不回,听牛友说要等9月投日常实习,现在都不招实习生了。各位牛友们看看还有哪些地方要改吗?
blue1031:
你是我见过最美的牛客女孩
点赞
评论
收藏
分享
07-29 17:46
长亭科技_政企_安服(实习员工)
7.25腾讯cisg--安全技术--青云计划--一面挂
两个面试官拷打我,真的是说到哪里,问到哪里,真的是太难啦,有种说不出来的感觉,月底面试像是kpi,但是又鼎着青云计划我还是老老实实沉淀沉淀吧
腾讯一面2194人在聊
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
都是 dirty work,为什么别人的简历上就能言之有物🤔
1.5W
2
...
百度提前批一面(秋招第一场也估计是压力最大的)
9531
3
...
秋招首凉-腾讯TEG 云架构平台提前批
5642
4
...
【07.29更新】能救一个是一个!26届毁意向毁约裁员黑名单
3999
5
...
团孝子启动ing!
3771
6
...
干活最少的实习生因为长得漂亮转正了
3222
7
...
虾皮后端一面(已挂)
2878
8
...
令人心动的offer!!!
2606
9
...
26滴滴秋招提前批Java一面
2519
10
...
27届前端实习该选哪个offer
2150
创作者周榜
更多
正在热议
更多
#
你遇到最难的面试题目是_
#
8450次浏览
115人参与
#
工作压力大怎么缓解
#
94111次浏览
994人参与
#
中兴秋招
#
197386次浏览
2209人参与
#
工作中哪个瞬间让你想离职
#
52528次浏览
460人参与
#
分享一个让你热爱工作的瞬间
#
32397次浏览
336人参与
#
你最讨厌面试问你什么?
#
16220次浏览
205人参与
#
腾讯大前端岗位热招中
#
71次浏览
1人参与
#
26届的你,投了哪些公司?
#
22839次浏览
280人参与
#
我对___祛魅了
#
33050次浏览
312人参与
#
简历上的经历如何包装
#
14740次浏览
513人参与
#
你跟室友的关系怎么样?
#
4291次浏览
77人参与
#
多益网络求职进展汇总
#
31499次浏览
140人参与
#
如何快速融入团队?
#
11871次浏览
142人参与
#
和同事相处最忌讳的是__
#
16153次浏览
160人参与
#
什么样的背景能拿SSP?
#
17805次浏览
136人参与
#
秋招前后对offer的期望对比
#
302533次浏览
2223人参与
#
打工人的精神状态
#
68412次浏览
1115人参与
#
饿了么求职进展汇总
#
64282次浏览
636人参与
#
我和mentor的爱恨情仇
#
62105次浏览
379人参与
#
实习生活中那些难忘的瞬间
#
165489次浏览
2458人参与
#
元戎启行求职进展汇总
#
36331次浏览
278人参与
#
牛友们的论文几号送审
#
48687次浏览
792人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务