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

yjjw 发表于 2020-12-7 02:38
想起在本科入门编程课学Racket时候老师的一句话"Trust the Natural Recursion!"

至理名言，可是面试就总想着是不是要记忆化啊，是不是要DP啊，不过第一步写完一个DFS的暴力会帮助优化思路，只是面试时不一定有这个时间

不知道小帅 发表于 2020-12-8 00:53
recursion确实不那么直观，不过其实处理这样的问题，首先要把你的function定义清楚，input是啥，output是啥 ...

有同感，recursion不直观我可以就想成一个blackbox，但是如你所说，首先要明确这个blackbox的定义，或者是接口，基本这个想明白了题也就解出来了。我只是纠结于，别的题想到特定的算法和数据结构也基本就做出来了，比如heap，双指针，拓扑排序，但是DFS问题即使想到用DFS，最难的部分是如何定义递归，弄清楚依旧完蛋，白高兴一场

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

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

牧moon 发表于 2020-12-8 01:58
有同感，recursion不直观我可以就想成一个blackbox，但是如你所说，首先要明确这个blackbox的定义，或者 ...

对，这个感觉靠经验和直觉比较多，其实dp也是一样的，先定义一个状态的表示，定义出来了，其实题目就做完一半了，很多时候只要有了状态表示，状态转移就类似于列一个方程了，也就没那么难了。