怎么优雅地使用 bottom up 解决 LeetCode 39. Combination Sum？
JasonLaw · 2020-11-15 16:15:51 +08:00 · 2126 次点击这是一个创建于 1470 天前的主题，其中的信息可能已经有所发展或是发生改变。
- top down: https://codeshare.io/5MdEkJ
- bottom up: https://codeshare.io/50kvxD
很明显，bottom up 比 top down 复杂多了，也更加难以理解，请问有什么优雅的方法实现 bottom up 吗？
第 1 条附言 · 2020-11-16 23:31:18 +08:00
其实是我自己的思维一直被局限住了，其实我完全可以换种方式思考这个问题。假设我有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
第 2 条附言 · 2020-11-16 23:37:33 +08:00
一个相关的视频：
 |
1
msg7086 2020-11-15 16:48:33 +08:00
bottom up 是什么思路？
这题第一感觉就是 BFS/DFS 和 DP 两种做法？ |
 |
2
zxCoder 2020-11-15 18:09:27 +08:00
什么叫做 bottom up
|
|
3
zxCoder 2020-11-15 18:10:15 +08:00
这不就是凑硬币的问题吗
|
 |
4
freakxx 2020-11-15 19:53:32 +08:00
@msg7086 #1
@zxCoder #2 他应该是想说自底向上， 类似动态规划写法。 直接参考这个吧。 https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/ |
 |
5
JasonLaw OP @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 版本，但是实现起来太复杂了，所以想问问有什么优雅的方式。 |
|
7
zxCoder 2020-11-15 21:03:37 +08:00
@JasonLaw 任何算法都可以通过 dfs 枚举解集来做，dp 也可以写成记忆化搜索的形式，就是你所说的 top down?
|
|
8
JasonLaw OP @zxCoder #7 你所说的 DFS 是不是就是递归？因为递归其实类似于 DFS，但是我感觉使用 DFS 不太适合，毕竟跟 search 毫无关系。还是说我有哪些东西不知道的？
|
 |
9
ericgui 2020-11-16 00:48:30 +08:00
|
|
10
ericgui 2020-11-16 01:02:10 +08:00
哦，但这个视频没讲你说的 bottom up
我也有疑问：什么是 bottom up ？ |
 |
11
beidounanxizi 2020-11-16 01:04:46 +08:00
亲 你好 么有优雅的 bottom up
另外， 题目刷的少 所以才会问这种🐶 |
 |
12
user8341 2020-11-16 01:17:07 +08:00
这道题似乎没办法用 DP 做。就算你记下重复的子问题的解，仍然要遍历复制解集中的所有元素——没有减少时间复杂度。
|
|
13
ericgui 2020-11-16 01:31:36 +08:00
https://leetcode.wang/leetCode-39-Combination-Sum.html
这个链接，讲了动态规划 但是吧，我咋感觉这代码那么墨迹呢 |
 |
14
nlzy 2020-11-16 03:34:36 +08:00
|
|
15
msg7086 2020-11-16 04:09:54 +08:00
@user8341 复制元素和重算解集的时间复杂度不是一个等级吧。
就算时间复杂度可能没减少，但是时间可是大幅减少的。 @JasonLaw 我说的 DFS/BFS 就是你说的递归。 可能的确不属于 search 不过解法是类似的，所以就习惯性说成了 D/BFS 。 这题我没有做过，所以就没代码可以上了。 但是你说 DP 解法看起来难以理解，可能是因为……是 Java 写的？ 我顺着上面的 C++版本抄了一份作业，看起来不是很复杂。 https://gist.github.com/msg7086/ce899c87ea7e72b790d03d85794ba2ee |
|
19
JasonLaw OP |
|
20
beidounanxizi 2020-11-16 23:52:46 +08:00
你刷的不够多 刷到 150 再来讨论更好
这是板子题差不多 或者就是 constructive algorithm 你再去看看 LEETCODE coin change 题目 你还要 dfs 么？ 多看别人题解 多做题就好了 骚年 |
|
21
beidounanxizi 2020-11-16 23:54:38 +08:00
还有 这个 YouTube 视频作者本身
只针对非常初级的 new beginner 合适 🐶 |
|
23
JasonLaw OP @beidounanxizi #20 我还是继续刷题吧💪
|
Select Language