回溯，递归，dp三法leetcode 题目“

leetcode 10 regular expression matching 可以减去一字符
leetcode wildcard matching 可以匹配一个字符
leetcode edit distance
回溯三要素：选择，限制条件，结束条件
回溯是一种算法思想，它是用递归实现的。回溯的过程类似于穷举法，但回溯有“剪枝”功能，即自我判断过程。例如有求和问题，给定有 7 个元素的组合 [1, 2, 3, 4, 5, 6, 7]，求加和为 7 的子集。累加计算中，选择 1+2+3+4 时，判断得到结果为 10 大于 7，那么后面的 5, 6, 7 就没有必要计算了。这种方法属于搜索过程中的优化，即“剪枝”功能。

回溯法解决leetcode10注意递归和回溯的区别
回溯具有剪枝的功能。当出现结束条件，自动回溯，不必再往不必要的地方搜索。

我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。
这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。

递归和回溯相关题目：
leetcode17 letter Combinations of a Phone Number
leetcode22 Generate Parentheses(最为经典)
leetcode46 permutations
在 Backtracking 标签中，有 30+ 道与递归、回溯相关的例题

回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。

http://www.cnblogs.com/shizhh/p/5302852.html 动态规划系列问题汇总