- top down: https://codeshare.io/5MdEkJ
- bottom up: https://codeshare.io/50kvxD
很明显，bottom up 比 top down 复杂多了，也更加难以理解，请问有什么优雅的方法实现 bottom up 吗？
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 2007 days ago, the information mentioned may be changed or developed.
Supplement 1 · Nov 16, 2020
其实是我自己的思维一直被局限住了，其实我完全可以换种方式思考这个问题。假设我有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
Supplement 2 · Nov 16, 2020
一个相关的视频：
 |
1
msg7086 Nov 15, 2020
bottom up 是什么思路？
这题第一感觉就是 BFS/DFS 和 DP 两种做法？ |
 |
2
zxCoder Nov 15, 2020
什么叫做 bottom up
|
|
3
zxCoder Nov 15, 2020
这不就是凑硬币的问题吗
|
 |
4
metamask Nov 15, 2020
@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 版本，但是实现起来太复杂了，所以想问问有什么优雅的方式。 |
|
8
JasonLaw OP @zxCoder #7 你所说的 DFS 是不是就是递归？因为递归其实类似于 DFS，但是我感觉使用 DFS 不太适合，毕竟跟 search 毫无关系。还是说我有哪些东西不知道的？
|
 |
9
ericgui Nov 16, 2020
|
|
10
ericgui Nov 16, 2020
哦，但这个视频没讲你说的 bottom up
我也有疑问：什么是 bottom up ？ |
 |
11
beidounanxizi Nov 16, 2020
亲 你好 么有优雅的 bottom up
另外， 题目刷的少 所以才会问这种🐶 |
 |
12
9LCRwvU14033RHJo Nov 16, 2020
这道题似乎没办法用 DP 做。就算你记下重复的子问题的解，仍然要遍历复制解集中的所有元素——没有减少时间复杂度。
|
|
13
ericgui Nov 16, 2020
https://leetcode.wang/leetCode-39-Combination-Sum.html
这个链接，讲了动态规划 但是吧，我咋感觉这代码那么墨迹呢 |
 |
14
nlzy Nov 16, 2020
|
|
15
msg7086 Nov 16, 2020
@user8341 复制元素和重算解集的时间复杂度不是一个等级吧。
就算时间复杂度可能没减少，但是时间可是大幅减少的。 @JasonLaw 我说的 DFS/BFS 就是你说的递归。 可能的确不属于 search 不过解法是类似的，所以就习惯性说成了 D/BFS 。 这题我没有做过，所以就没代码可以上了。 但是你说 DP 解法看起来难以理解，可能是因为……是 Java 写的？ 我顺着上面的 C++版本抄了一份作业，看起来不是很复杂。 https://gist.github.com/msg7086/ce899c87ea7e72b790d03d85794ba2ee |
|
18
9LCRwvU14033RHJo Nov 16, 2020
@msg7086 你这么说好像有道理。大佬是不是两种实现都做过？能不能贴个代码让我学习一下？
|
|
19
JasonLaw OP |
|
20
beidounanxizi Nov 16, 2020
你刷的不够多 刷到 150 再来讨论更好
这是板子题差不多 或者就是 constructive algorithm 你再去看看 LEETCODE coin change 题目 你还要 dfs 么？ 多看别人题解 多做题就好了 骚年 |
|
21
beidounanxizi Nov 16, 2020
还有 这个 YouTube 视频作者本身
只针对非常初级的 new beginner 合适 🐶 |
|
23
JasonLaw OP @beidounanxizi #20 我还是继续刷题吧💪
|
Select Language