算法思想
# 数论算法
数论思想：利用数学公式或者定理或者规律求解问题； 如最大公约数、质数等等。 这些可简单可复杂，重点在于理解问题。
# 分治算法
# 基本特征
- 问题缩小到一定规模容易解决
- 分解成的子问题是相同种类的子问题，即该问题具有最优子结构性质
- 分解而成的小问题在解决之后要可以合并
- 子问题是相互独立的，即子问题之间没有公共的子问题
# 和其他的不同。
第二条的大多数问题也可以满足，反应的是递归的思想。 第三条这个是能分治的关键，解决子问题之后如果不能合并从而解决大问题的话。 可以考虑贪心或者dp
# 步骤
- 分解成很多子问题
- 解决这些子问题
- 将解决的子问题合并从而解决整个大问题 和递归一样，只是就是一个表达式。
# 回溯算法
回溯算法，又称为“试探法”。 解决问题时，每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。 这种走不通就回退再走的方法就是回溯算法。
例如，在解决列举集合 {1,2,3} 中所有子集的问题中，就可以使用回溯算法。 从集合的开头元素开始，对每个元素都有两种选择：取还是舍。 当确定了一个元素的取舍之后，再进行下一个元素，直到集合最后一个元素。 其中的每个操作都可以看作是一次尝试，每次尝试都可以得出一个结果。将得到的结果综合起来，就是集合的所有子集。
# 枚举算法 | 暴力破解 | 枚举法
即对可能的解集合一一列举。
枚举算法的实现往往通过使用循环（嵌套）就能够轻易实现，所以并没有什么思维难度。
# 递归
# 思考
1.微信分销系统中有一个返利，大家应该都知道， 比如B是A的下线，C是B的下线，那么在分钱返利的时候A可以分B，C的钱， 这时候我们是不是就要分别找B,C的最后上级。这个问题我们一般怎么来解决呢？
A->B->C
2.斐波那契数列： 1 1 2 3 5 8 13 21 有什么特点？ 从第三个数开始 就等于前面两个数相加；
3.重要性 算法思想中最难的点：递归+动态规划（可以不用太懂）；树论：二叉树，红黑树。里面大量用到递归。
# 什么是递归？
# 递归的定义：
递归是一个非常重要的算法思想，应用也是相当的广泛，包括我们后面学的数据结构尤其是树形结构里面跟递归是密不可分的。 所以大家是一定要学懂它的，其实递归说起来很简单，生活中也是经常可以碰到这个场景。
比如我们在某窗口排队人太多了，我不知道我排在第几个，那么我就问我前面的人排第几个， 因为知道他排第几我就知道我是第几了。但前面的人也不知道自己排第几那怎么办呢？他也可以继续往前面问，直到问到第一个人，然后从第一个人一直传到我这里 我就很清楚的知道我是第几了。 以上这个场景就是一个典型的递归。 我们在这个过程中大家有没有发现一个规律那么就是会有一个问的过程， 问到第一个后有一个回来的过程吧。这就是递（问）加归（回）。
那么这个过程我们是不是可以用一个数学公式来求解呢？那这个数学公式又是什么？ f(n)=f(n-1)+1 f(n):表示我的位置 f(n-1):表示我前面的那个人；
总的来说，就是自己调用自己； 递归就是来 回的过程。一般可以用公式表示。 2种思想，递归的过程和回溯过程。
# 什么样的情况下可以用递归？
（1）一个问题的解可以分解为几个子问题的解：子问题，我们通过分治的思想可以把一个数据规模大的问题，分解为很多小的问题。 我们可以把刚刚那个问前面的那个人看为子问题。大化小
（2）这个问题与分解之后的子问题，求解思路完全一样： 也就是说f(n) 和 f(n-1) 一样
（3）一定有一个最后确定的答案，即递归的终止条件：刚刚那个问题就是第一个人。第一个人是肯定知道自己排第几吧即n=1的时候。 如果没有这个特性那么我们这个递归就会出现死循环，最后程序就是栈溢出；stack out of
# 递归的实现
3.递归如何实现？里面有哪些算法思想？ 递归，回溯； 2种思想，递归的过程和回溯过程。 递归的关键相信大家已经知道了就是要求出这个递归公式，找到终止条件。现在我们可以回到课堂前跟大家讲的那个斐波那契数列数列： 1 1 2 3 5 8 13 这个的数列我们称之为斐波那契数列 所以重点就是2个：
- 他的求解公式：f(n)=f(n-1)+f(n-2)
- 终止条件：n<=2 f(n)=1
# 递归分析
4.递归的时间和空间复杂度分析： 因为是来回的操作，所以时间复杂度是乘以2。 可以忽略，但实际损耗是挺大的。
- 递归算法的时间复杂度：递归的总次数*每次递归的数量。
- 递归算法的空间复杂度：递归的深度*每次递归创建变量的个数。
以斐波那契数列为例为分析递归树： f(n)=f(n-1)+f(n-2) 关键他会产生一个递归树，所以O(2^n)
分析一段代码好坏，有两个指标，时间复杂度和空间复杂度 他都是：O(2^n)
# 递归的优化
目标往 O(2^n) =》 O(n^2) =>O(n)或者O(nlogn)
性能问题的原因:
- 递归容易重复计算（不一定），所以这也是优化的一个点。 如缓存优化。 在归来的时候就附上值了。
- 递归对于编译器来说，会创建大量的栈空间。
- 对于有计算的递归，还是创建临时变量和栈空间。
优化方式： (1)使用非递归。所有的递归代码理论上是一定可以转换成非递归的。 (2)加入缓存：把我们中间的运算结果保存起来，这样就可以把递归降至为o(n) (3)尾递归：什么是尾递归？尾递归就是调用函数一定出现在末尾，没有任何其他的操作了(不会在做计算如 f(n-1)+1 )。 因为我们编译器在编译代码时，如果发现函数末尾已经没有操作了，这时候就不会创建新的栈，而是覆盖到前面去。 尾递归就是传入结果，倒着算，不需要在回溯了，因为我们每次会把中间结果带下去。同时也没有了中间重复的操作，这样也快了。
注意尾递归的两个点： 1. 不能再做计算 2. 传入结果，倒着算。 具体感悟:
尾递归就是传入结果，倒着算。这样把回溯的过程去掉了。直接放回。 把表达式当做结果参数去传。几个fn 就是几个结果参数。 他其实是for循环的升级版。
// 斐波那契数列： 1 1 2 3 5 8 13 21 ; f(n)=f(n-1)+f(n-2)
public static int fibonacciFor(int n){
int res = 0;
int last = 1;
int last2 = 1;
for (int i = 3; i <= n; i++) {
res = last + last2;
last = last2;
last2 = res;
}
return res;
}
public static int fibonacciTail(int n,int last,int last2){
if(n < 3){
return last;
}else{
return fibonacciTail(n-1,last2 + last,last);//fibonacci(n-1) + fibonacci(n-2);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 递归和其他的不同
# 递归和迭代有什么区别 ？
1.递归的基本概念:程序调用自身的编程技巧称为递归,是函数自己调用自己.一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量. 2.迭代:利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。 3.递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。
# 递归和回溯的区别
- 递归是一种算法结构,递归会出现在子程序中,形式上表现为直接或间接的自己调用自己;
- 而回溯是一种算法思想,它是用递归实现的,回溯的过程类似于穷举法,但回溯有“剪枝”功能,即自我判断过程。
# 递归和分治有什么区别吗？
递归是一种写代码的技巧，本质是自己调用自己。分治是一种解决问题的方法
分治一定有合并的操作，递归却不一定有。
一般递归，分治往往是在一起的 。 也就是说分治一般用递归来实现。
# 递归总结
递归最重要。是一定要掌握的，这里面有一个尾递归，可能很多同学还没想清楚的，后面多看看我的视频回放注意尾递归的两个点。 递归确实是一个写代码的神器可以看起来代码整洁以及可读性高。 但是使用起来一定要注意，栈溢出和时间问题。 不太清楚的情况下，就是用for循环或者使用数组保存中间结果。
递归的好处，简单便于理解。
递归都可以改成for循环，加缓存，尾递归。
建议改成for循环来代替递归。
最终::::
在有公式成立时，可以用递归过渡；
对于有操作的，之后还是要优化成for循环。
没有操作的可以看做尾递归不做优化。
2
3
4
5
6
7
# 贪心算法 | 贪婪算法 | 登山算法（一定需要掌握）
# 概念
它在求解某个问题是，总是做出眼前最大利益。 也就是说只顾眼前不顾大局，所以它是局部最优解。 核心点：通过局部最优推出全局最优。
# 例子
某天早上公司领导找你解决一个问题，明天公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束时间，你怎么样安排才能使会议室最大利用？即安排最多场次的会议？ 0点~9点：9点之前开始的会议都不行了。 8点~10点 10点~12点：12点 8点~20点 现在我们怎么去贪？也就这个我们选择的贪心策略： 时间最短？开始时间？结束时间？ 等等策略 解题思路： 按结束时间从小到大排序：首先把第一个加入我们可以开会的列表。之后只要开始时间是大于我们上一个的结束时间的就可以开。统计最大的。
# 编码
只能多用测试用例。 不能证明出来其中的公式。 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
# 使用条件
- 贪心选择性质
并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。 局部最优解->全局最优解
- 最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 该性质动态规划也有，分支也有。重点还是第一条。
# 核心点
贪心算法其最重要的两个点就是：贪心策略，排序 局部最优解->全局最优解。是贪心算法与动态规划算法的主要区别。
# 贪心策略
不是对所有问题都能得到整体最优解，通过局部最优解能够得到全局最优解，关键是贪心策略的选择。 选择的贪心策略必须具备无后效性： 也就是说某个状态以前的过程不会影响以后的状态，只与当前状态有关。
# 排序
一定会有一个排序。（按对应的策略）
# 应用场景
一般有以下问题就可以通过贪心算法解决：
- 针对某个问题有限制值，以及有一个期望的最好（最值）结果；通常是从某些数据中选出其中一些，达到最好（最值）的结果。
- 一般会有一个排序，找出贡献最大（最值）的。
- 举例看贪心是否可以解决。
一般用在任务调度，教师排课等系统。 哈夫曼编码，贪心算法，压缩算法，最短路径等最值问题。 找零钱的问题（每次找最大的）。
# 总结
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，（类似于尾递归）因此贪心算法与其他算法相比具有一定的速度优势。 如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
# 动态规划 | DP算法 (最难，可以不学)
实际上，用贪心算法解决问题的思路，并不总能给出最优解，比如来看下一个问题：
# 思考
经典问题：背包问题 小偷去某商店盗窃，背有一个背包，容量是50kg，现在有以下物品（物品不能切分,且只有一个），请问小偷应该怎么拿才能得到最大的价值？ 重量 价值 物品1 10kg 60元 60 / 10 = 6 物品2 20kg 100元 100/20 = 5 物品3 40kg 120元 120/40 = 3 很显然最高值为：40+10（kg）=120+60=180 解法一: 性价比最高：贪心的策略，按性价比排序,得到的最大价值是 60+100=160，背包装了30kg。 贪心是解决不了的。 解法二: 暴力破解: 遍历它：每个物品只有2个选择就是拿与不拿吧，我们就用枚举，排列组合； 时间复杂度最高n! 算不出来的情况是有的。
# 概念
可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。 因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。
# 适用条件
- 最优子结构性质
- 无后效性
- 子问题的重叠性
一般用动态规划可以解决的问题：
- 局部最优解：也就是它会有一个最优子结构
- 子问题可以重复
- 状态转移方程 (VC)： 和概念对应
通过把问题分成很多小阶段一段段的转移。从而得出最优解.状态转移方程是解决动态规划的关键。 如果我们能写出状态转移方程，那动态规划问题基本上就解决一大半了，翻译成代码非常简单。 但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到。
# 编码实现
求解的基本步骤: (1)划分阶段: 按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。 (2)确定状态和状态变量: 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程 : 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。 也可以根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 (4)寻找边界条件 ： 给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般也常用递归来实现。
# 动态规划矩阵
一般采用动态规划矩阵来实现。判断状态。 时间复杂度O(n*m)
- 矩阵类动态规划，也可以叫做坐标类动态规划，一般这类问题都会给你一个矩阵，矩阵里面有着一些信息，然后你需要根据这些信息求解问题。
- 在思考这类动态规划问题的时候，我们只需要思考当前位置的状态，然后试着去看当前位置和它邻居的递进关系，从而得出我们想要的递推方程
- 好多其他的问题都可以转化为矩阵去实现。
# 应用
1.求解最值问题：最短路径经典算法 2.短字符相似性匹配 3.策略问题: 4.哈夫曼编码
# 和遍历（暴力破解）的比较及优化：
遍历每次在物品加进来的时候都会保存选择与不选择两种状态那么这样下去越到后面状态保存的就越多其实就是2^n次，因为每个物品都有选与不选两种情况。 而动态规划是每次都会把当前情况下的最优解计算出来，层层递推，下一层的最优解都是基于它上一次结果存下来的，所以最后一个结果就一定是最优解。 其实也是把问题都分解成了一个子问题，然后通过子问题去求解全局最优解。但是可以过滤很多重复的操作。
# 动归和贪心的比较：
贪心是只管眼前不会管后的情况，而动归不一样，它的每次递推都是基于上一次的最优解进行。 所以往往动归是一定能求出最优解的，而贪心不一定，这也是贪心算法的缺点。 但是大家都看到了动归的时间复杂度是O(n*m)而贪心是O(nlogn)，所以贪心算法的是高效的，动归如果子问题太多的话 就容易算不出结果，而且能用动归的问题往往用贪心都能解决一部分，甚至很大一部分。 因此如果在实际项目中要求不是特别严的话 我建议使用贪心算法求最优解，其实我们很多时候并不用保证100%的准确，能尽量准确就可以了，贪心恰恰是符合这个规则的。
# 总结
动态规划Dp，ms很喜欢问背包问题、警察抓小偷。
部分问题，可以用贪心算法来实现。
状态转移方程，是实现的主要逻辑。
他可以减少枚举方法的比较次数。 他主要是以加入物品的状态，通过矩阵来判断。
# 参考资料
比较困难的题目。
- 一次性弄懂到底什么叫做分治思想 (opens new window)
- 以斐波那契数列为例分析递归算法的时间复杂度和空间复杂度 (opens new window)
- 带你逐步分析递归算法的时间复杂度 (opens new window)
f(n) = f(n)*n 这种是O(n) ; f(n)=f(n-1)+f(n-2) 这是 2^(n-2) + 2^(n-3) ... + 2^1 + 2^0 等于 2^n
- 递归和回溯的区别 (opens new window)
- 回溯算法详解 (opens new window)
- 【算法】枚举算法 (opens new window)
- 算法学习-暴力破解！枚举法（穷举法） (opens new window)
暴力破解最常用的就是枚举法，也叫穷举法。 最差但是通用的解题思路。
经典例子: 活动安排问题,找零钱问题,背包问题（个别情况实现不了，得用dp算法）,均分纸牌,最大整数
求解的基本步骤; 经典问题：找零钱问题、走方格问题、走台阶问题、最长公共序列数
例子： 路径问题， 最大正方形的面积，
AC自动机主要用于解决多模式串的匹配问题，是字典树(trie树)的变种