觉得DFS实现起来要比其他的算法困难？

不知道还有没有小伙伴有这样的感觉，我在刷题的时候经常感到DFS实现的时候思路特别不清晰，但是一看答案恍然大悟，比如Leetcode 282 Expression add operations这道题，就是一个正常的DFS搜索，也能在纸上画出graph的构图，可是实现的时候发现 1+, 1-, 1*，这咋更新，卡了一会又去想别的乱七八糟的思路，结果一看答案发现就是常规DFS，但是变成+1, -1, *1这种搜索思路就直观多了。
虽然其他的题也有看答案之后恍然大悟的感觉，但是大多是没想到特定的算法或者是数据结构，比如原来这道题要用heap，原来这道题要用双指针等等，而这样的题在想到这些算法和数据结构往往就迎刃而解了。搜索的问题，一般能看出BFS，我感觉写起来也比较顺畅。但是我个人一碰到DFS，不算动态规划这种高级DFS，就容易发生这种思路混乱，就是即使知道是DFS能画出graph，也还是容易卡在实现上，可能归根结底还是对递归的定义不清晰吧。想看看地里的小伙伴有没有这样的问，是不是我缺少练习，应该集中专攻一下。互相交流一些练习方法，或者就吐吐槽发泄一下！


补充内容 (2020-12-8 01:42):
Update：
哎呀，没想到这么多小伙伴给出很多好的建议和共鸣，我打算像下面一位同学说的去leetcode找dfs或者backtracking专题做一些题。也谢谢小伙伴给出的对recursion加强理解的建议，没有那么多大米，不能一一分米

补充内容 (2020-12-8 01:45):
有一个地方我没有描述清楚，我觉得我对DFS和递归这些概念理解的还可以，backtracking的专题中以前也做过一些高频的，比如像combination，permutation，leetcode 17这样的DFS题，写的还是比较顺畅的。

补充内容 (2020-12-8 01:49):
但是像282那样的题，知道要用DFS递归，但还是对递归方程的定义，像下面同学说的，input，output，这个递归做什么，感到非常困惑。估计这也是题目的难点，好歹是hard，就算有思路DFS，难点在于怎么定义graph和分解

在282 Expression Add Operators的题目描述中，当有经验的同学看到题目说“return all possibilities to add binary operators”的时候，就自然想到用backtracking做了，因为backtracking可以暴力枚举所有的possible solutions（当然有时候dfs/backtracking不是最优解）。

建议重点刷DFS和Backtracking的tag（10-20题），之后你再看到类似的题目就会立马想到用dfs/backtracking做了。

而且似乎工作里用的也不多，也确实难

想起LinkedIn 里一个大哥，stripe 的发了一个post，2年了，终于在工作里实现了一个dfs

牧moon 发表于 2020-12-8 01:53
至理名言，可是面试就总想着是不是要记忆化啊，是不是要DP啊，不过第一步写完一个DFS的暴力会帮助优化思 ...

DP的题目一般来说问题还是不太一样的，DP的话一般是最大，最小，可能的总数，是否存在之类的。
输出所有可能结果的话还得是dfs/backtracking。

想起在本科入门编程课学Racket时候老师的一句话"Trust the Natural Recursion!"

我也有同样的感觉！导致现在看到tree和recursion就害怕😂

dfs是最简单的，因为有套路且corner case好处理

确实挺难的 需要多做题

recursion确实不那么直观，不过其实处理这样的问题，首先要把你的function定义清楚，input是啥，output是啥，这个函数做了什么事。语义一定要清楚，然后递归调用的时候就根据语义来就好了，从一个更小规模的input怎么得到当前input所对应的output。至于更小规模的那个问题，我们不需要考虑是怎么处理的，甩锅给下一层递归就好了。只需要考虑语义和转换关系就够了。然后就是给个终止条件，也就是base case。

a_small_potato 发表于 2020-12-7 01:36
在282 Expression Add Operators的题目描述中，当有经验的同学看到题目说“return all possibilities to ad ...

谢谢你的建议，打算集中刷几个backtracking的高频练习一下，以前只注意公司分类，还真没注意topic分类，给你加个米