312. Burst Balloons 真的会有公司考吗？

Vicmal 发表于 2019/06/23 16:01:12
DP题刷少了吧，这种题我当年高中noip的时候最多算个二维区间DP入门题，多刷点各种类型的DP，像这种看出来是区间DP，但是如果常规定义状态又不符合DP的基本要求，那就可以想想合并区间以后有什么不变量...

哪里有比较好的DP题集（有解答代码的）？谢了！

前段时间刷过这题，当时是理解了，过了一个月再回头，dp是如何推导的都忘了

这题还是有点tricky的地方，比如说算dp[1][1]只有一个元素时要把左边右边的balloon也都算上，也是奇特

所以DP题应该怎么刷。。。。

zorrowei 发表于 2019-6-26 01:17
求大神说一下扫描线的经典题目都有啥？谢了！

有个倒水的好像是起步题目吧，leetcode769是我被google面过原题……其实思路就是如果n2的复杂度不行，排序也没有明显作用，就该考虑双指针或者扫描线

kzhu 发表于 2019-6-23 17:07
dp可以用递归做，俗名记忆化搜索，常常比递推做更方便

老哥，记忆化dfs超时了，能帮看下我code有啥问题么？https://pastebin.com/8AGuzzWK

这就和dijstra一样，不背下来你在现场是想不出来的。。

cecilianxf 发表于 2019-10-16 17:44
这就和dijstra一样，不背下来你在现场是想不出来的。。

dijstra    想了20分钟，面试给你40分钟很合理 ：）

donezio 发表于 2019-10-16 23:36
dijstra    想了20分钟，面试给你40分钟很合理 ：）

关键greedy算法tricky之处在于，你很难在短时间内证明她的正确性。所以只能靠背。。。因为万一你想错了就很麻烦。（这也是面试很少考greedy的原因—）

当然了，常见的greedy可能还是会考。比如dij这种。

这题第一次见的时候想了10分钟，20分钟左右蠡口过了把。。。

其实你简历越好经验越多，越不会碰到这种题，你看像Homebrew这种大牛Google都是出逆转二叉树这种题