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

[JasonLaw]

题目：Combination Sum - LeetCode

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

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

其实是我自己的思维一直被局限住了，其实我完全可以换种方式思考这个问题。假设我有coins为[1, 2, 5]，target为5。我之前是将原问题拆分为“coins为[1, 2, 5]，target为4”、“coins为[2, 5]，target为3”、“coins为[5]，target为0”三个子问题，但是我完全可以将原问题拆分为“coins为[1, 2, 5]，target为4”、“coins为[2, 5]，target为5”两个子问题。

下面是优化之后的版本：

• top down: https://codeshare.io/aVLx8R
• bottom up: https://codeshare.io/GAPxwe

一个相关的视频：

[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 谢谢。