蝈蝈店面面经

bdhmwzfa · 2018-10-21 16:36:06

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

x

只进行了一轮电面，题目之前没在地里看到过，分享出来给大家

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

我用的动态规划做的，比如dp[i][j]表示在第i行，收集完这一行以及前面所有的糖果之后停在第j列，最少需要多少步
大概思想就是这个
最后漏掉了一个corner case，就是如果发现某行以下已经完全没有糖果了，就不需要继续走了。。。
如果大家觉得有用的话，给加点大米吧，谢谢各位

zhongyh · 2018-10-21 23:19:07

没有必要对所有位置做DP，只需要考虑每行最左及最右的石子位置即可，没有石子的行直接直行，所以可以省略

bdhmwzfa · 2018-10-22 09:28:27

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

bdhmwzfa · 2018-10-23 08:42:06

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

dengzeyu147 · 2018-10-21 22:34:59

楼主有空的话能列个dp式子嘛已加米

bdhmwzfa · 2018-10-22 09:20:05

zhongyh 发表于 2018-10-21 23:19
没有必要对所有位置做DP，只需要考虑每行最左及最右的石子位置即可，没有石子的行直接直行，所以可以省略

没错，其实只需要考虑从最左和最右端下来就行了
但是其基本思想依然是借助子问题最优解进行递推的过程，所以说是dp的思想

archonsh · 2018-10-22 09:43:41

但是在dp的时候也要考虑有折返的情况吗

bdhmwzfa · 2018-10-22 09:54:31

archonsh 发表于 2018-10-22 09:43
但是在dp的时候也要考虑有折返的情况吗

需要考虑，从上一行跳下来之后，直到从本行某一位置跳下去，是可能在本行出现折返的

paladin12 · 2018-10-22 10:48:51

bdhmwzfa 发表于 2018-10-22 09:54
需要考虑，从上一行跳下来之后，直到从本行某一位置跳下去，是可能在本行出现折返的

意思是还可以往上走？

补充内容 (2018-10-22 10:54):
哦哦，理解了！

金妮韦崽 · 2018-10-22 15:02:27

请问楼主是面的intern吗

bdhmwzfa · 2018-10-22 15:22:48

金妮韦崽发表于 2018-10-22 15:02
请问楼主是面的intern吗

不是，是FTE