未分類
1 11 月 2020

怎么优雅地使用 bottom up 解决 LeetCode 39. Combination Sum？

怎么优雅地使用 bottom up 解决 LeetCode 39. Combination Sum？

資深大佬 : JasonLaw 4

题目：Combination Sum – LeetCode

  • top down: https://codeshare.io/5MdEkJ
  • bottom up: https://codeshare.io/50kvxD

很明显，bottom up 比 top down 复杂多了，也更加难以理解，请问有什么优雅的方法实现 bottom up 吗？

大佬有話說 (26)

  • 資深大佬 : msg7086

    bottom up 是什么思路？
    这题第一感觉就是 BFS/DFS 和 DP 两种做法？

  • 資深大佬 : zxCoder

    什么叫做 bottom up

  • 資深大佬 : zxCoder

    这不就是凑硬币的问题吗

  • 資深大佬 : freakxx

    @msg7086 #1
    @zxCoder #2

    他应该是想说自底向上，
    类似动态规划写法。

    直接参考这个吧。
    https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/

  • 主 資深大佬 : JasonLaw

    @msg7086 #1
    @zxCoder #2

    @freakxx #4 说的是对的，我说的是动态规划中的自底向上。

    @freakxx #4 我最开始就是写出了类似 https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/ 中的算法，但是那个算法做了一些不需要做的事情，比如 candidates 是[1, 2]，target 是 3，那么算法会产生[[1, 1, 1], [1, 2], [2, 1]]，注意[1, 2]和[2, 1]是重复的。其实我们完全可以避免这样的情况，这也是 https://codeshare.io/5MdEkJ 中算法所能实现的。

    而 https://codeshare.io/50kvxD 是 https://codeshare.io/5MdEkJ 的 bottom up 版本，但是实现起来太复杂了，所以想问问有什么优雅的方式。

  • 主 資深大佬 : JasonLaw

    @msg7086 #1 我有点好奇，用 BFS/DFS 怎么实现呢？可以分享一下你的代码吗？

  • 資深大佬 : zxCoder

    @JasonLaw 任何算法都可以通过 dfs 枚举解集来做，dp 也可以写成记忆化搜索的形式，就是你所说的 top down?

  • 主 資深大佬 : JasonLaw

    @zxCoder #7 你所说的 DFS 是不是就是递归？因为递归其实类似于 DFS，但是我感觉使用 DFS 不太适合，毕竟跟 search 毫无关系。还是说我有哪些东西不知道的？

  • 資深大佬 : ericgui

    https://www.bilibili.com/video/BV1854y1m7WR

    这个视频讲 39 题

  • 資深大佬 : ericgui

    哦，但这个视频没讲你说的 bottom up

    我也有疑问：什么是 bottom up ？

  • 資深大佬 : beidounanxizi

    亲 你好 么有优雅的 bottom up
    另外， 题目刷的少 所以才会问这种

  • 資深大佬 : user8341

    这道题似乎没办法用 DP 做。就算你记下重复的子问题的解，仍然要遍历复制解集中的所有元素——没有减少时间复杂度。

  • 資深大佬 : ericgui

    https://leetcode.wang/leetCode-39-Combination-Sum.html

    这个链接，讲了动态规划

    但是吧，我咋感觉这代码那么墨迹呢

  • 資深大佬 : nlzy

    https://gist.github.com/Nlzy/8e5f3773a37946f9f1434756c1d3ebad

  • 資深大佬 : msg7086

    @user8341 复制元素和重算解集的时间复杂度不是一个等级吧。
    就算时间复杂度可能没减少，但是时间可是大幅减少的。

    @JasonLaw 我说的 DFS/BFS 就是你说的递归。
    可能的确不属于 search 不过解法是类似的，所以就习惯性说成了 D/BFS 。
    这题我没有做过，所以就没代码可以上了。

    但是你说 DP 解法看起来难以理解，可能是因为……是 Java 写的？
    我顺着上面的 C++版本抄了一份作业，看起来不是很复杂。

    https://gist.github.com/msg7086/ce899c87ea7e72b790d03d85794ba2ee

  • 主 資深大佬 : JasonLaw

    @ericgui #9 说实话，视频太啰嗦了

  • 資深大佬 : ericgui

    @JasonLaw 嗯，确实啰嗦，我也知道，但我假设听众是小白。

  • 資深大佬 : user8341

    @msg7086 你这么说好像有道理。大佬是不是两种实现都做过？能不能贴个代码让我学习一下？

  • 主 資深大佬 : JasonLaw

    @msg7086 @zxCoder @freakxx @ericgui @beidounanxizi @user8341 @nlzy 大家好，我在附言中优化了算法，有兴趣可以看看。

  • 資深大佬 : beidounanxizi

    你刷的不够多 刷到 150 再来讨论更好
    这是板子题差不多 或者就是 constructive algorithm

    你再去看看 LEETCODE coin change 题目 你还要 dfs 么？

    多看别人题解 多做题就好了 骚年

  • 資深大佬 : beidounanxizi

    还有 这个 YouTube 视频作者本身
    只针对非常初级的 new beginner 合适

  • 資深大佬 : zxCoder

    @JasonLaw 你想太复杂了，这就是一个最基础的 dp，自顶向下写法就是记忆化搜索

  • 主 資深大佬 : JasonLaw

    @beidounanxizi #20 我还是继续刷题吧

  • 主 資深大佬 : JasonLaw

    @zxCoder #22 需要多练，有时候就是想不出更加好的方法。

  • 資深大佬 : zxCoder

    @JasonLaw 是的 其实做这种算法题需要思考，但是也需要有一定的题量作为基础

  • 主 資深大佬 : JasonLaw

    @zxCoder #25 谢谢。