想问点回溯法和DP的问题
来源：9-1 什么是动态规划
慕数据3866775
2018-11-10
bobo老师你好，我想问关于backtracking、DFS和DP的两个问题。
1）在我的理解当中，这几类题：a）通常求极值（包括最大最小值，最长最短等，例如leetcode第5题最长回文子串），b）某个方案可行不可行（比如leetcode第139题word break等），c）以及一些distinct的方案的总数（比如第60题Unique Path，第70题Climb Stairs等）；然后backtracking的题通常都是用来解所有排列组合的题（比如第10题Regular Expression Matching 以及一堆Permutation Combination Subsets相关的题）。
然后我今天做93-Restore IP Addresses的时候，审题的时候如下
然后突然想到70-Climbing Stairs，如下图
这两道题代码部分我能看懂也能写，但是对回溯法和DP深层次的理解有问题，你看红框和红线的部分，比如93题是求“所有”组成的可能性，70题是求“所有”不一样（distinct）的路径，都是求“所有”的解决方案，为什么93题是用回溯法，70题则是动态规划？这两个“所有”有什么区别？当我遇到新的没见过的算法题的时候，如何才能甄别该用上面写的第c类的DP问题或者是用回溯法呢？
2）回溯法和DFS的区别是什么？我查了一些资料（比如这个链接：https://stackoverflow.com/questions/1294720/whats-the-difference-between-backtracking-and-depth-first-search），
说回溯法是思想，DFS是其中的一种实现，我的理解是回溯法是每个解法都去试试，不行就返回，中间不保存树形结构；而DFS则会保留树形结构，避免重复计算。请问这个理解有没有错误？有没有别的更好的理解方式呢？
非常感谢！
1回答
-
第二个问题比较好回答。理解成DFS和回溯没有区别是没问题的。至少我就是这么理解的。只不过在具体用语上，回溯更倾向于是一种算法设计思想，而DFS更像是一个具体的实现手段。
==========
对于第一个问题，你可能还需要再仔细理解一下我在这个课程所布置的第八，九两章的整体课程设计思路。
尤其是在第九章，讲动态规划的时候，每一个算法我都配合写了一遍记忆化搜索。为什么？因为记忆化搜索本质是回溯搜索的一个优化。由于在回溯搜索的过程中，有大量的重复子问题，所以可以使用记忆化搜索。而动态规划是将这个求解过程从递归转成了递推，或者说从自顶向下转成了自底向上。
所以，不能通过问题类型来推断用什么方法。回溯和动态规划是可以解决同类问题的。在我看来，对于任何一个问题，都可以尝试先使用回溯的方式解决（搜索是计算机领域的万金油的方法，所有的任务总能搜出来），然后在这个过程中，看是否有重叠子问题，如果有，就能用动态规划！
当然，在具体的问题中，有可能你尝试使用回溯法，发现数据规模肯定超时，同时貌似没有重叠子问题，那么在这种情况下，一种可能是有更适合动态规划（或者记忆化搜索）的状态定义方式。（也可以理解成是搜索方式）。
请仔细体会一下背包问题，想一想，如果你没有学过背包算法的话，搜索你会怎么做，但是背包算法的记忆化搜索在怎么搜，这二者有什么区别？
当然，不见得所有你尝试回溯超时的算法，都可以转为动态规划，也有可能是数据结构问题，或者数学问题。找到合适的算法解决问题本身就是算法设计中非常关键的一环。需要大量的练习培养自己的直觉和对问题以及条件的敏感。在我看来，没有一个规则，遵守这个规则，就能找到正确的算法，解决所有问题：）
加油！：）
012018-11-10
相似问题