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