其实动态规划是不是就是DFS的升级版啊？

RT, 楼主发现用DFS做某些题目会超时，而用DP做就不会，感觉是因为DP把中间运行的值存起来了方便以后用，是不是这么一回事啊？。。。楼主初来乍到...问题弱智求别喷...

DP能解决的问题，DFS都能解决，感觉DP是把DFS中的一类有特殊性质的问题提炼出来了吧

动态规划其中的一部分又叫记忆化搜索（或者这俩都是一个东西？有点忘了）
通常的dfs做了很多重复的搜索，即在参数一样的情况下因为递归所以重复搜了很多次造成时间更长
经常情况下dfs是指数级而DP可以降到平方甚至线性

DP不完全算是DFS的升级版，因为DFS只是搜索中的一类=。=
要说的话应该是所有搜索的升级版吧~

楼主所言极是。

今天看CC150，在Graph那一章看到：DP算法由于会记忆中间结果，因此其效率很高

递归是自顶向下，DP是自底向上。

这两个不能这么比吧。。。
DP is a mathematical optimization and programming method. For many complex problems, there are many subproblems sharing the similar structure. Take advantage of this property. Optimize the algorithm by using the things you have computed and stored. Usually, algorithm with exponential running time could be reduced to polynomial running time.

DFS is just a algorithm to traverse a tree or a graph, nothing special......

DP是思想, dfs是实现
就像
Mapreduce是思想,hadoop是实现

DP 是一种内隐式的列举法(implicit enumeration)，把一个大问题分散成很多子问题，让你不必把所有的可能组合都列出来就可以找到最佳解，想要知道DP的核心思想可以看一下驿马车问题(Stage coach problem)，我会说DP不是一种算法，是一种逻辑推导的方式

然后DP的问题由前往后做和由后往前做都会得到一样的答案，不影响，它困难的地方是在于不同的题目有不同的切入方式，但大体而言都是把State、Stage、Recursive Function这几个关键的东西找出来就很好求解了

记忆化搜索就可以看作是DP，避免了重复计算。

个人理解，DP一方面是化整为零、化大为小（这一点是说有的问题直接做甚至都没有思路，从DP看却可能有突破口）， 另一个就是避免重复计算（可能有了一种算法能解决问题，但是DP能让算法更有效率）。

DP可以是递归的形式（使用memorization, 比如wordladder II）， 也可以不是递归的形式（比如longest palindrome substring， path sum）。 而DFS通常是递归的形式，当然也可以不是，但是当DFS是非递归的时候，也很难和DP进行比较。

说 DP 是升级版的DFS 并不稳妥。我更倾向于Readman说的DP是一种思想。 使用DP必须对问题有一个清晰的认识，对不同级别规模问题(n vs n-1 / n-2 / ...)之间的联系和转换有把握（以公式的形式严格表达出来）。