一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
查看: 551|回复: 4
收起左侧

[动态规划] 面试如果被问到DP的题目

[复制链接] |只看干货 |刷题, 动态规划
我的人缘0

升级   8.14%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (46)
 
 
0% (0)    👎

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

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

x
敢不敢上来就给最优化的解法?

还是需要按部就班:
第一步: Intuitively, use recursive
第二步: 优化recursive  with Top down DP
第三步: 优化Top down with bottom up DP
第四步: More tricks for final optimization

感觉4部的戏会比较足   上来就给最优解    后面剩的时间演什么?

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:请问java 刷题 有好的博主可以看吗?
下一篇:SWE实习面试前,要把非SWE面经也刷了吗?求大佬指点。
我的人缘0

升级   47.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (65)
 
 
0% (0)    👎
最好简单说一下brute force然后之间说dp解。感觉四步曲写不完implementation?

评分

参与人数 1大米 +1 收起 理由
14417335 + 1

查看全部评分

回复

使用道具 举报

我的人缘0

升级   8.14%

 楼主| myonlysunshine 2020-10-22 04:02:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (46)
 
 
0% (0)    👎
MachaIceCream 发表于 2020-10-22 03:31
最好简单说一下brute force然后之间说dp解。感觉四步曲写不完implementation?

四个都写肯定写不完   需要有侧重

最后一步最优解肯定要写 (如果能写出来)

第一步如果简单也写一下   中间挑一个写写?  其他略过

这样安排怎么样  
回复

使用道具 举报

我的人缘0

升级   52.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (787)
 
 
7% (62)    👎
1. 第一步可以省略,除非不能一下子看出可以用 dp 解。
2. top down 还是 bottom up 无所谓,给出状态转移方程就行。
3. 并不一定要写完再优化空间,可以先分析 dp 矩阵和运行方式,怎么优化写的时候心里自然就有数了,简单的题这个其实挺一目了然的。
4. 复杂一点的 dp 题面试的时候可能没时间优化,建议 2 和 3 要先做,这样就算写完没时间改也可以简单叙述一下让面试官清楚思路,比如股票四那道题。

评分

参与人数 2大米 +4 收起 理由
逆风局局长i + 2 很有用的信息!
myonlysunshine + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   47.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (65)
 
 
0% (0)    👎
myonlysunshine 发表于 2020-10-21 13:02:08
四个都写肯定写不完   需要有侧重

最后一步最优解肯定要写 (如果能写出来)
第一步讲思路 之后直接讲二/三的解法。个人觉得四可能没空 让面试官follow up就好。求米求米。

评分

参与人数 1大米 +2 收起 理由
myonlysunshine + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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