二叉树（binary tree）是树的一种特殊形式，是N（N>=0）个结点的有限集合，该集合或为空集（空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。二叉，顾名思义，这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。

二叉树节点的两个孩子节点，一个被称为左孩子（left child），一个被称为右孩子（right child）。这两个孩子节点的顺序是固定的，左孩子小于右孩子。

特点

每个结点最多只有两颗子树
左右子树是有顺序的
即使某结点只有一颗子树，也要区分是右子树还是左子树

满二叉树

所有分支结点都存在左子树和右子树，并且所有非叶子节点都在同一层上。

完全二叉树

一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。

满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

二叉树的存储

二叉树属于逻辑结构，可以使用链表和数组进行存储。

链式存储

二叉树的每一个节点包含3部分：存储数据的data变量；指向左孩子的left指针；指向右孩子的right指针

数组存储

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来

寻址方式

一个父节点的下标是n，那么它的左孩子节点下标就是2×n+1、右孩子节点下标就是2*(n+1) 对于一个稀疏的二叉树（孩子不满）来说，用数组表示法是非常浪费空间的所以二叉树一般用链表存储实现。（二叉堆除外）

3.二叉查找树

概念

二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序。

综上所述,在二叉树中:

1:若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值
2:任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3:任意节点的左、右子树也分别为二叉查找树；
4:没有键值相等的节点。

二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。

查找过程实例

例如查找值为4的节点，步骤如下：

1. 访问根节点6，发现4<6。
2. 访问节点6的左孩子节点3，发现4>3
3. 访问节点3的右孩子节点4，发现4=4，这正是要查找的节点

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。这种方式正是二分查找思想。

插入过程实例

例如插入新元素5，步骤如下：

1. 访问根节点6，发现5<6
2. 访问节点6的左孩子节点3，发现5>3
3. 访问节点3的右孩子节点4，发现5>4
4. 5最终会插入到节点4的右孩子位置

二叉树的遍历

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。

①深度优先遍历

所谓深度优先，顾名思义，就是偏向于纵深，“一头扎到底”的访问方式。它包括:

前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树(根左右)

步骤如下：

1、首先输出的是根节点1
2、由于根节点1存在左孩子，输出左孩子节点2
3、由于节点2也存在左孩子，输出左孩子节点4
4、节点4既没有左孩子，也没有右孩子，那么回到节点2，输出节点2的右孩子节点5
5、节点5既没有左孩子，也没有右孩子，那么回到节点1，输出节点1的右孩子节点3
6、节点3没有左孩子，但是有右孩子，因此输出节点3的右孩子节点6

到此为止，所有的节点都遍历输出完毕

中序遍历

二叉树的中序遍历，输出顺序是左子树、根节点、右子树（左根右）

步骤如下：

1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2、依照中序遍历的次序，接下来输出节点4的父节点2
3、再输出节点2的右孩子节点5
4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的根节点1
5、由于节点3没有左孩子，所以直接输出根节点1的右孩子节点3
6、最后输出节点3的右孩子节点6

到此为止，所有的节点都遍历输出完毕

后序遍历

二叉树的后序遍历，输出顺序是左子树、右子树、根节点（左右根）

步骤如下：

1、首先访问根节点的左孩子，如果这个左孩子还拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，并输出该节点。显然，第一个没有左孩子的节点是节点4
2、输出右节点5
3、输出节点4的父节点2
4、以节点2为根的左子树已经输出完毕，这时再输出整个二叉树的右子树
5、访问根节点的右孩子，如果这个右孩子拥有左孩子，则继续深入访问下去，一直找到不再有左孩子的节点，如果没有左孩子则找右孩子，并输出该节点6
6、输出节点6的父节点3

到此为止，所有的节点都遍历输出完毕

②广度优先遍历

也叫层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

二叉树同一层次的节点之间是没有直接关联的，利用队列可以实现

1、根节点1进入队列

2、节点1出队，输出节点1，并得到节点1的左孩子节点2、右孩子节点3。让节点2和节点3入队

3、节点2出队，输出节点2，并得到节点2的左孩子节点4、右孩子节点5。让节点4和节点5入队

4、节点3出队，输出节点3，并得到节点3的右孩子节点6。让节点6入队

5、节点4出队，输出节点4，由于节点4没有孩子节点，所以没有新节点入队

6、节点5出队，输出节点5，由于节点5同样没有孩子节点，所以没有新节点入队

7、节点6出队，输出节点6，节点6没有孩子节点，没有新节点入队

时间复杂度

二叉查找树的插入和查找时间复杂度为:O(logn) 极端情况下二叉查找树退化成链表，时间复杂度为O(n)，所以需要平衡二叉查找树。

应用

非线性数据：菜单，组织结构、家谱等等

线性数据：二叉查找树

二叉查找树是有序的，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

二叉查找树的性能非常稳定，扩容很方便(链表实现)

3.红黑树

概念

红黑树（Red Black Tree）也是一种自平衡二叉查找树，它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树并不追求AVL树般的严格平衡，减少了平衡所需的操作，从而提高性能。红黑树的应用非常广泛，Java中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的，除此之外，Node.js的定时器管理中也有红黑树的存在。

平衡二叉查找树

这种二叉查找树就退化成了链表，由于树的深度变得多了，查找的效率也会大幅下降。所以需要对这种二叉树进行自平衡，红黑树就是一种自平衡的二叉查找树。

特点

每个节点要么是黑色，要么是红色
根节点是黑色
每个叶子节点都是黑色的空结点（NIL结点）（为了简单期间，一般会省略该节点）
如果一个节点是红色的，则它的子节点必须是黑色的（父子不能同为红）
从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点（平衡的关键）
新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡

一颗典型的红黑树：

在对红黑树进行添加或者删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特点，从而维持平衡。主要通过修改颜色（颜色反转）和旋转节点（左旋转、右旋转）来完成平衡。

平衡流程可查看《红黑树维持平衡的方式解析》

时间复杂度：

O(logn)

应用

在JDK1.8中HashMap使用数组+链表+红黑树的数据结构。内部维护着一个数组table，该数组保存着每个链表的表头结点或者树的根节点。HashMap存储数据的数组定义如下，里面存放的是Node实体：


transient Node<K, V>[] table;//序列化时不自动保存
/*** 桶的树化阈值：即 链表转成红黑树的阈值， * 在存储数据时，当链表长度 > 该值时，则将链表转换
成红黑树 */ static final int TREEIFY_THRESHOLD = 8;

4.多路查找树

概念

多路查找树(muitl-way search tree)，其每一个节点的孩子数可以多于两个，且每一个节点处可以存储多个元素。

B树

B树（BalanceTree）是对二叉查找树的改进。它的设计思想是，将相关数据尽量集中在一起，以便一次读取多个数据，减少硬盘操作次数。
一棵m阶的B 树 (m叉树)的特性如下：
B树中所有节点的孩子节点数中的最大值称为B树的阶，记为M
树中的每个节点至多有M棵子树 ---即：如果定了M，则这个B树中任何节点的子节点数量都不能超过M
若根节点不是终端节点，则至少有两棵子树
除根节点和叶节点外，所有点至少有m/2棵子树
所有的叶子结点都位于同一层

B+树

B+树是B-树的变体，也是一种多路搜索树，其定义基本与B树相同，它的自身特征是：

非叶子结点的子树指针与关键字个数相同

非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树

为所有叶子结点增加一个链指针

所有关键字都在叶子结点出现

数据结构和算法的可视化网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

典型应用

MySQL索引B+Tree

B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。多叉平衡

B树的高度一般都是在2-4这个高度，树的高度直接影响IO读写的次数。
如果是三层树结构---支撑的数据可以达到20G，如果是四层树结构---支撑的数据可以达到几十T B和B+的区别
B树和B+树的最大区别在于非叶子节点是否存储数据的问题。
B树是非叶子节点和叶子节点都会存储数据。
B+树只有叶子节点才会存储数据，而且存储的数据都是在一行上，而且这些数据都是有指针指向的，也就是有顺序的。

5.二叉堆

二叉堆本质上是一种完全二叉树，它分为两个类型

1. 大顶堆(最大堆)

最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值

2. 小顶堆(最小堆)

最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值

二叉堆的根节点叫作堆顶

最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素

二叉堆的存储原理

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2 的节点，右子节点就是下标为 i∗2+1 的节点，父节点就是下标为 i/2 取整的节点

二叉堆的典型应用

优先队列

利用堆求 Top K问题

在一个包含 n 个数据的数组中，我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了

二、排序

1.冒泡排序

冒泡排序（bubble sort）是最基础的排序算法。它是一种基础的交换排序。冒泡排序这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点地向着数组的一侧移动。

按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。

经过第一轮后：元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧

每一轮结束都会有一个元素被移到最右侧

冒泡排序的优化

外层循环优化

第6轮已经可以结束了，也就是如果不需要交换了，则说明已经排好序了

内层循环优化

已经被移到右侧的元素不用再参与比较了

时间复杂度：O(n^2)

2.快速排序

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分，这种思路就叫作分治法。

基准元素的选择

基准元素(pivot)，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边，我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置

元素的交换

选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素另一边。

双边循环法

首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素

第1次循环：从right指针开始，让指针所指向的元素和基准元素做比较。如果大于或等于pivot，则指针向左移动；如果小于pivot，则right指针停止移动，切换到left指针。轮到left指针行动，让指针所指向的元素和基准元素做比较。如果小于或等于pivot，则指针向右移动；如果大于pivot，则left指针停止移动，左右指针指向的元素交换位置，由于left开始指向的是基准元素，判断肯定相等，所以left右移1位

由于7>4，left指针在元素7的位置停下。这时，让left和right指针所指向的元素进行交换。

接下来，开始第二次循环：重新切换到right指针，向左移动。right指针先移动到8，8>4，继续左移。由于2<4，停止在2的位置

单边循环法

单边循环法只从数组的一边对元素进行遍历和交换。

开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。

接下来，从基准元素的下一个位置开始遍历数组。如果遍历到的元素大于基准元素，就继续往后遍历。如果遍历到的元素小于基准元素，则需要做两件事：

把mark指针右移1位，因为小于pivot的区域边界增大了1；
让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域

首先遍历到元素7，7>4，所以继续遍历。

接下来遍历到的元素是3，3<4，所以mark指针右移1位

随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。

按照这个思路，继续遍历，后续步骤如图所示

快速排序的时间复杂度：O(nlogn)

3.堆排序

TODO

4.计数排序

TODO

5.桶排序

TODO

三、字符串匹配

TODO

四、图

TODO

五、算法思维

1.贪心算法

概念

是一种在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。贪婪算法：当下做局部最优判断，不能回退（能回退的是回溯，最优+回退是动态规划）

在贪婪算法(greedy method) 中，我们要逐步构造一个最优解。每一步，我们都在一定的标准下，做出一个最优决策。做出决策所依据的标准称为贪心准则(greedy criterion)。

贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。
也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法每一步必须满足以下条件：
　　1、可行的：即它必须满足问题的约束。
　　2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
　　3、不可更改：即选择一旦做出，在算法的后面步骤就不可改变了。

注意:!!!
贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

案例

钱币找零问题

假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来找给顾客K元，怎么用数目最少的钱来找零？

贪心准则:在不超过要找的零钱总数的条件下，每一次都选择面值尽可能大的纸币，直到凑成的零钱总数等于要找的零钱总数。


#include<iostream>
 
using namespace std;
 
int min(int a, int b) {
	return a < b ? a : b;
}
int main()
{
	//人民币面值集合
	int values[] = { 1, 2, 5, 10, 20, 50, 100 };
	//各种面值对应数量集合
	int counts[] = { 3, 1, 2, 1, 1, 3, 5 };
	//求442元人民币需各种面值多少张
	//用来记录需要的各种面值张数
	int money = 442;
	int len = sizeof(values) / sizeof(values[0]);
	int* result = new int[len];
	for (int i = len - 1; i >= 0; i--) {
		int num = 0; //当前面值纸币的数量
		num = min(money / values[i], counts[i]); //当前纸币可以找的最大数量
		money = money - num*values[i];
		result[i] = num;
	}
	//输出最后结果
	for (int i = 0; i < len; i++) {
		if(result[i])
			cout << "需要面额为" << values[i] << "的人名币" << result[i] << "张\n";
	}
	cout << endl;
 
	system("pause");
	return 0;
}

程序结果:

需要面额为2的人名币1张
需要面额为5的人名币2张
需要面额为10的人名币1张
需要面额为20的人名币1张
需要面额为100的人名币4张

可以得出，求出的结果为最优解，但是，当纸币面值和数量为某些特殊情况下，贪心算法就无法给出最优解。但是，贪心算法往往能给出近似解，对于我们来说也是有价值的。

比如对于纸币有1、5、7面值的若干，要凑出10元
贪心解[3,0,1]
最优解[0,2,0]

贪心算法的基本思路

1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

贪心算法最优性证明

贪心算法的前提

贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
关键是贪心策略的选择，而贪心算法与动态规划的主要区别是:
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。即贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。
所以，贪心算法的正确性可以通过数学归纳法或贪心交换来给予证明。

最优子结构

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

贪心算法与动态规划的区别

贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。
贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
能用贪心解决的问题，也可以用动态规划解决

时间复杂度

在不考虑排序的前提下，贪心算法只需要一次循环，所以时间复杂度是O(n)

优缺点

优点：性能高，能用贪心算法解决的往往是最优解

缺点：在实际情况下能用的不多，用贪心算法解的往往不是最好的

适用场景

针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据（局部最优而全局最优）

大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明在实际情况下，用贪心算法解决问题的思路，并不总能给出最优解

贪心算法的经典问题

0/1背包问题

最优解

2.分治算法

概念

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

算法设计思想：
分（divide）：递归解决较小的问题（基本情况除外）。
治（conquer）：从子问题的解构建原问题的解。

适合用分治法的问题：
当求解一个输入规模非常大的问题时，用暴力法效率一般得不到保证，如果问题能满足以下几个条件，就可以采用分治法提高解决效率：

能将这n个数据分解成k个不同的子集合，且得到k个子集合是可以独立求解的子集问题，1<k<=n
分解所得到的子问题与原问题具有相似的结构，便于利用递归或循环机制
在求出子问题的解可以推出原问题的解。

时间复杂度

根据拆分情况可以是O(n)或O(logn)

优缺点

优势：将复杂的问题拆分成简单的子问题，解决更容易，另外根据拆分规则，性能有可能提高。

劣势：子问题必须要一样，用相同的方式解决

适用场景

典型采用分治算法的例子：二分法查找，归并排序，快速排序，二叉树遍历（先遍历左子树再遍历右子树），二叉排序树的查找等算法。

3.回溯算法

概念

回溯法思路的简单描述是：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。

回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。

回溯的处理思想，有点类似枚举（列出所有的情况）搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

时间复杂度

N皇后问题的时间复杂度为：O(n!)实际为n!/2

优缺点

优点：回溯算法的思想非常简单，大部分情况下，都是用来解决广义的搜索问题，也就是，从一组可能的解中，选择出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，我们并不需要穷举搜索所有的情况，从而提高搜索效率。

劣势：效率相对于低（动态规划）

适用场景

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了

4.动态规划

概念

动态规划(Dynamic Programming)，是一种分阶段求解的方法。动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现. 关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式) 我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该讲最优解保存下来, 为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度

动态规划中有三个重要概念：

最优子结构
边界
状态转移公式（递推方程）dp方程

经典问题

斐波那契数列

时间复杂度

新的斐波那契数列实现时间复杂度为O(n)

优缺点

优点：时间复杂度和空间复杂度都相当较低

缺点：难，有些场景不适用

适用场景

尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/501268