怎么优雅地使用 bottom up 解决 LeetCode 39. Combination Sum?
题目:Combination Sum – LeetCode
- top down: https://codeshare.io/5MdEkJ
- bottom up: https://codeshare.io/50kvxD
很明显,bottom up 比 top down 复杂多了,也更加难以理解,请问有什么优雅的方法实现 bottom up 吗?
题目:Combination Sum – LeetCode
很明显,bottom up 比 top down 复杂多了,也更加难以理解,请问有什么优雅的方法实现 bottom up 吗?
他应该是想说自底向上,
类似动态规划写法。
直接参考这个吧。
https://leetcode-cn.com/problems/combination-sum/solution/chao-qiang-gifzhu-ni-shi-yong-dong-tai-gui-hua-qiu/
@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 版本,但是实现起来太复杂了,所以想问问有什么优雅的方式。
这个视频讲 39 题
我也有疑问:什么是 bottom up ?
这个链接,讲了动态规划
但是吧,我咋感觉这代码那么墨迹呢
@JasonLaw 我说的 DFS/BFS 就是你说的递归。
可能的确不属于 search 不过解法是类似的,所以就习惯性说成了 D/BFS 。
这题我没有做过,所以就没代码可以上了。
但是你说 DP 解法看起来难以理解,可能是因为……是 Java 写的?
我顺着上面的 C++版本抄了一份作业,看起来不是很复杂。
https://gist.github.com/msg7086/ce899c87ea7e72b790d03d85794ba2ee
你再去看看 LEETCODE coin change 题目 你还要 dfs 么?
多看别人题解 多做题就好了 骚年