很多人认为回溯和递归是一样的，其实不然。在回溯法中可以看到有递归的身影，但是两者是有区别的。
回溯法从问题本身出发，寻找可能实现的所有情况。和穷举法的思想相近，不同在于穷举法是将所有的情况都列举出来以后再一一筛选，而回溯法在列举过程如果发现当前情况根本不可能存在，就停止后续的所有工作，返回上一步进行新的尝试。
递归是从问题的结果出发，例如求 n！，要想知道 n！的结果，就需要知道 n*(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)*(n-2)!。这样不断地向自己提问，不断地调用自己的思想就是递归。
使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。
例如，在解决列举集合{1,2,3}所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：
回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的答案。图 1 中的状态树是满二叉树，得到的叶子结点全部都是问题的解。
在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，有时会发现此种情况下，
再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。
9、动态规划(DP)算法动态规划过程：每一次决策依赖于当前的状态，即下一状态的产生取决于当前状态。一个决策序列就是在变化的状态中产生的，这种多阶段最优化问题的求解过程就是动态规则过程。
基本思想原理
与分而治之原理类似，将待求解的问题划分成若干个子问题（阶段）求解，顺序求解各个子问题（阶段），前一子问题（阶段）为后一子问题（阶段）的求解提供有用的信息。
通过各个子问题（阶段）的求解，依次递进，最终得到初始问题的解。一般情况下，能够通过动态规划求解的问题也可通过递归求解。
动态规划求解的问题多数有重叠子问题的特点，为了减少重复计算，对每个子问题只求解一次，将不同子问题（阶段）的解保存在数组中。
与分而治之的区别：
分而治之得到的若干子问题（阶段）一般彼此独立，各个子问题（阶段）之间没有顺序要求。而动态规划中各子问题（阶段）求解有顺序要求，具有重叠子问题（阶段），后一子问题（阶段）求解取决于前一子问题（阶段）的解。
与递归区别：
与递归求解区别不大，都是划分成各个子问题（阶段），后一子问题（阶段）取决于前一子问题（阶段），但递归需要反复求解同一个子问题（阶段），相较于动态规划做了很多重复性工作。
适用解决问题
采用动态规划求解的问题一般具有如下性质：
- 最优化原理：求解问题包含最优子结构，即，可由前一子问题（阶段）最优推导得出后一子问题（阶段）最优解，递进得到初始问题的最优解。
- 无后效性：某状态以后的过程不会影响以前的状态，只与当前状态有关。
- 有重叠子问题：子问题（阶段）之间不是独立的，一个子问题（阶段）的解在下一子问题（阶段）中被用到。（不是必需的条件，但是动态规划优于其他方法的基础）
比如斐波那契数列，就是一个简单的例子。
定义：
Fab(n)= Fab(n-1) Fab(n-2)
Fab(1)=Fab(2)=1;
实现1：
static int GetFab(int n)
{
if (n == 1) return 1;
if (n == 2) return 1;
return GetFab(n - 1) GetFab(n - 2);
}
假如我们求Fab(5) 。那我们需要求Fab（4） Fab（3）。
Fab(4)=Fab(3) Fab(2).....显然。 Fab（3）被计算机不加区别的计算了两次。而且随着数字的增大，计算量是指数增长的。
如果我们使用一个数组，记录下Fab的值。当Fab(n)!=null 时。
直接读取。那么，我们就能把时间复杂度控制在 n 以内。
实现2：
static int[] fab = new int[6];
static int GetFabDynamic(int n)
{
if (n == 1) return fab[1] = 1;
if (n == 2) return fab[2] = 1;
if (fab[n] != 0)//如果存在，就直接返回。
{
return fab[n];
}
else //如果不存在，就进入递归，并且记录下求得的值。
{
return fab[n] = GetFabDynamic(n - 1) GetFabDynamic(n - 2);
}
}
这就是，动态规划算法的 备忘录模式。只需要把原来的递归稍微修改就行了。
下面是0-1背包问题的解法。
可以对比一下。（一个限重w的背包，有许多件物品。sizes[n]保存他们的重量。values[n]保存它们的价值。求不超重的情况下背包能装的最大价值）
static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分别为3, 4, 7, 8, 9 且是不可分割的 0-1 背包问题
static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的价值分别为4, 5, 10, 11, 13
static int capacity = 16;
static int[,] dp = new int[6, capacity 1];
static int knapsack(int n, int w)
{
if (w < 0) return -10000;
if (n == 0) return 0;
if (dp[n, w] != 0)
{
return dp[n, w];
}
else
{
return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) values[n - 1]);
/*
* knapsack(n,w) 指在前N件物品在W剩余容量下的最大价值。
* 这个公式的意思是，对于某一件物品，
* 1、如果选择装进去，那么，当前价值=前面的n-1件物品在空位w - size(n)下的最大价值（因为空位需要留出，空位也隐含了价值）。
* 再加上这件物品的价值。等于 knapsack(n - 1, w - size[n - 1]) values[n - 1]
* 2、 如果我们选择不装进去，那么，在n-1物品的情况下空位仍然在，当前价值 = 前面n-1件物品在空位w下的最大价值。
* 等于knapsack(n - 1, w)
* 注意：随着演算，某一情况下的价值不会一成不变。
* 此时我们做出决策：到底是在装入时的价值大，还是不装入时的价值大呢？我们选择上面两种情况中值较大的。并记录在案。
* 最后dp[N,M]就是我们要求的值。
*/ }
}10、字符串匹配算法
字符串匹配问题的形式定义：
- 文本（Text）是一个长度为 n 的数组 T[1..n]；
- 模式（Pattern）是一个长度为 m 且 m≤n 的数组 P[1..m]；
- T 和 P 中的元素都属于有限的字母表 Σ 表；
- 如果 0≤s≤n-m，并且 T[s 1..s m] = P[1..m]，即对 1≤j≤m，有 T[s j] = P[j]，则说模式 P 在文本 T 中出现且位移为 s，且称 s 是一个有效位移（Valid Shift）。
比如上图中，目标是找出所有在文本 T = abcabaabcabac 中模式 P = abaa 的所有出现。
该模式在此文本中仅出现一次，即在位移 s = 3 处，位移 s = 3 是有效位移。
解决字符串匹配的算法包括：
- 朴素算法（Naive Algorithm）、
- Rabin-Karp 算法、
- 有限自动机算法（Finite Automation）、
- Knuth-Morris-Pratt 算法（即 KMP Algorithm）、Boyer-Moore 算法、Simon 算法、Colussi 算法、Galil-Giancarlo 算法、Apostolico-Crochemore 算法、Horspool 算法和 Sunday 算法等）。
字符串匹配算法通常分为两个步骤：预处理（Preprocessing）和匹配（Matching）。所以算法的总运行时间为预处理和匹配的时间的总和。
上图描述了常见字符串匹配算法的预处理和匹配时间。
这里设计的很多，大家可以根据需求学习指定算法。
如果本文对你有帮助，别忘记给我个3连 ，点赞，转发，评论，学习更多JAVA知识与技巧，关注与私信博主（888）白嫖Java相关资料，路线、进阶、面试等等。
,
