花花酱 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers - 刷题找工作 EP298

[@hengchunsong301]

听花花一席话，胜自己瞎折腾十小时。昨天想破脑袋也没明白为什么自己的解法超时。原来递归加记忆是记录了字符串位置而不是字母本身。到后面的降围优化又让我看懂一些高手的答案为啥那么快。

[@HuaHuaLeetCode]

用位置的话是O(n^3)，感觉有些勉强

[@dionwang]

优化思路牛逼

[@sakuragi1111]

比如你有三个手指，多个手指都一样...一本正经地搞笑😂

[@lobsterl6286]

left right finger 不是index 而是上一步的所有可能性，这一步解释的太好了。。。看别人的答案一直迷糊为什么不是上一步的index，想不明白这一步的话dp根本没法优化时间。

[@xianjuwang1123]

我还是没想明白，这个解法是按顺序打印，题目上没有这样说。

[@xinyuanliu1959]

请问是如何想到从两个手指到一个手指的优化呢？

[@jasonsun8202]

huahua 最近用fp风格写cpp了啊！

[@HuaHuaLeetCode]

懒得传参数

[@jasonsun8202]

cpp closure 不错。不过你的function 式dfs 有时候 会引起type erasure 和用到heap space。

[@jasonsun8202]

用这个。 template struct recursive { F f; template decltype(auto) operator()(Ts&&... ts) const { return f(std::ref(*this), std::forward(ts)...); } template decltype(auto) operator()(Ts&&... ts) { return f(std::ref(*this), std::forward(ts)...); } }; template recursive(F) -> recursive; auto const rec = [](auto f){ return recursive{std::move(f)}; };

[@jasonsun8202]

而且可以使用 optional monad 继续优化和解耦。

[@jasonsun8202]

@@HuaHuaLeetCode lambda 是default inline 的好像。

[@chaopei9357]

这个是不是算greedy啊？

[@Anonymous____________A721]

Optimized dp