MapBox OA 一脸懵逼的DP题

题目和iceInMyVeins大大发的完全一致，我就直接上连接了。
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=576389&highligh

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

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

new Comparator<Integer>()  .....

第三题
力克扣得 狗撕屋
没啥好说的，直接变体一下就好了

lupeiqing 发表于 2019-12-13 01:21
请问楼主有没用presum数列啊？怎么计算和存储啊

用了 presum 的数列

大概举个例子应该就懂了， 例如给了[1, 3, 6]

1. presum = [0, 1, 4, 10]
   
2. dp = [[1, 3, 6],
   
3.      [-1, -3, 0],
   
4.      [9, 0, 0]]
   
5.          

复制代码

直接写了2-D DP好懂点，但是可以直接改成1D的。

钢铁侠吉米 发表于 2019-12-12 04:46
我也刚做完。第一题太坑了……
我只写出来递归做法。DP实在是没写出来。6个case都超时了。唉……凉了

摸摸层主，其实这题你用memo的话，把递归的结果存起来就可以了....

钢铁侠吉米 发表于 2019-12-12 04:46
我也刚做完。第一题太坑了……
我只写出来递归做法。DP实在是没写出来。6个case都超时了。唉……凉了

一模一样啊，6个cases昨天写了我一晚上，哎，凉了。

我也刚做完。第一题太坑了……
我只写出来递归做法。DP实在是没写出来。6个case都超时了。唉……凉了

wangdiao01 发表于 2019-12-12 05:15
一模一样啊，6个cases昨天写了我一晚上，哎，凉了。

我就是dp[n][n]的两个坐标如何决定没搞出来。我写的不对……唉，还是太菜

钢铁侠吉米 发表于 2019-12-12 04:46
我也刚做完。第一题太坑了……
我只写出来递归做法。DP实在是没写出来。6个case都超时了。唉……凉了

楼主最后解决了吗

wangdiao01 发表于 2019-12-12 05:15
一模一样啊，6个cases昨天写了我一晚上，哎，凉了。

层主，最后解决了吗

请问楼主有没用presum数列啊？怎么计算和存储啊

lupeiqing 发表于 2019-12-13 01:20
层主，最后解决了吗

没有，优化了1个小时搞不出来放弃了。垃圾hackerrank。
去准备亚麻面试去了

这个题整整花了我一个下午！（怒摔！