黑车面精

店面 HackerRank上的题

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

暴力dp：
首先去了再回=两条路线
dp, f[i][j][k] = 两条路线走到了第i行，第1条路线末端在第j列，第二条路线末端在第k列，两条路线的最后一步都是down，的情况下最多能采集多少宝石
f[i][j][k] = max_{jj, kk} f[i - 1][jj][kk] + g(i -1, jj, kk, j, k)
g(i -1, jj, kk, j, k)  = "从i－1行jj kk这个位置向右走到j k这个位置然后向下不算重复之后得了多少分“，我们的定义限定了从上一行到这一行一定是先往右再往下的，所以很好实现.
O(N^5)


补充内容 (2018-10-31 08:44):
我脑残了，正解差不多是这个意思但是n^3就行

fdsscz 发表于 2018-10-31 08:38
好像是  利口 其肆意
（我看了楼上回复搜草莓发现搜不到 是采樱桃。。。）

还真是...没做到这题 摔。。。

lookwinwin 发表于 2018-11-1 20:56
店面出这种题，面试官损人品啊~~~
祝福楼主

谢谢 两天没消息 估计是跪了...

补充一下 折返的时候只可以move up or move left

就是离口采草莓那道题啊

感觉正向可以用dp 存每一点最大collect数目
如果可以track所走的路线
set取过的1为0
再dp一次 找一个新的路线？

drool 发表于 2018/10/31 08:01:47
就是离口采草莓那道题啊

大侠请留下题号？！

好像是  利口 其肆意
（我看了楼上回复搜草莓发现搜不到 是采樱桃。。。）

两遍dp不能解决问题。（ 741）

？？？？？这个店面过分了