查看: 1159| 回复: 4
收起左侧

[动态规划] [求解答]二维矩阵dp题

匿名用户-PVIVZ  2020-12-28 03:18:31
本楼:   👍  0
0%
0%
0   👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
求教大佬们一道题。2D矩阵要从左上到达右下,每次步长等于所在位置的值,可以向右或向下走,求最少步数。因为有时间限制,所以应该是得用dp做,想问下具体思路和实现。在此提前感谢!

Screen Shot 2020-12-27 at 9.42.08 AM.png

上一篇:LC每日的challenge题目有什么特别的吗?
下一篇:寻找一个小伙伴互相讲题,本人easy/Medium水平
shaoli12800 2020-12-28 03:38:59 来自APP | 显示全部楼层
本楼:   👍  1
100%
0%
0   👎
全局:   1344
96%
4%
60
最简单直观的应该是recursion+memo 然后再推dp
回复

使用道具 举报

nevergum 2020-12-28 07:36:46 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   173
97%
3%
6
先建立一个1对多的map,next(i,j) = {(i.,j) 下一步能到达的坐标}。
利用这个next mapping, 反过来 建立mapping, prev(i,j) = {走一步能到达(i,j)的坐标}
有了这个准备数据 就可以DFS - 从右下开始,找到一步到达右下的所有坐标,赋值1 (步);对这些值为1的坐标,找到他们的上一步,如果没被赋值过的,赋值2;然后继续这样赋值3,4.。。直到找到左上坐标,其赋值就是解; 如果拓展到停止还没到左上 则无解。
回复

使用道具 举报

chubaka123 2020-12-28 08:44:25 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   2233
87%
13%
337
本帖最后由 somesaywithme 于 2020-12-28 08:45 编辑

这题(或者类似的)思路可以这样:
对这个矩阵的每个元素,它可以由哪几个点跳过来?取这些点里最小move的,加一,就成了当前这个点的move数。那最后就return 右下的那个就行了。

那如何求每个元素比如(i,j)是由哪几个点跳过来的呢?我觉得可以先遍历一边:对每个元素,“它可以到哪些点” (有点反向思考)。遍历完成的时候,我们就知道了每个元素是由那些点跳过来的。这样就有了之前我们需要的信息。

回复

使用道具 举报

14417335 2020-12-28 23:05:11 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   599
99%
1%
7
抱歉您不能对匿名帖评分

题目挺好的对jump game的扩展。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表