数据结构与算法思维导图模板_ProcessOn思维导图、流程图

排序

要点

时间复杂度

空间复杂度

稳定性

在一个待排序的数据中存在多个值相等的元素，经过稳定算法排序之后，相等元素之间的原有的先后顺序不变

原地性

不需要申请新的存储空间来存储待排序数据

原地排序空间复杂度不一定是 O(1)

空间复杂度为 O(1)的排序算法肯定是原地排序算法

稳定排序

冒泡排序

原理

每个元素和相邻的元素比较，不符合条件的交换位置

代码实现

算法分析

时间复杂度

最好情况：O(n)，完全顺序

最坏情况：O(n^2)，完全逆序

平均时间复杂度 O(n^2)

空间复杂度

O(1)

原因是只是在本地进行交换，并没有行进多余的空间创建

是不是原地排序

是

是不是稳定排序

是

插入排序

原理

将数组中的数据分为：已排序区间 和 未排序区间

初始已排序区间只有一个元素，就是数组中的第一个元素

核心思想是：取未排序区间中的元素，
在已排序区间中找到合适的插入位置将其插入(遍历倒序已排序区间)，
保证已排序区间数据一直有序

代码实现

算法分析

时间复杂度

最好情况：O(n)，数据是顺序的

最坏情况：O(n^2)，数据是逆序的

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

空间复杂度

O(1)

是否是原地排序

是

是否是稳定排序

是

选择排序

原理

讲数组划分为 已排序区间 和 未排序区间
初始，已排序区间为空，未排序区间为整个数组
遍历未排序区间，找到最小的元素放入到已排序区间的末尾

代码实现

算法分析

时间复杂度

最好情况：O(n)，数据是顺序的

最坏情况：O(n^2)，数据是逆序的

平均时间复杂度O(n^2)

空间复杂度

O(1)

是否是原地排序

是

是否是稳定排序

否

它对比数据之后是有一个交换操作，比当前数小就会交换
[2，6，4，2，3，1] 第一次交换后[1，6，4，2，3，2]
原来的 2 挪到最后去了，并且它之前还有一个2，这个2会优先操作

归并排序

原理

把一个数组从中间分成两部分，分别对其进行排序，然后把两个已经排序好的数组合并

递归，问题拆分成最小子问题，这里的数组，最后就拆分成了一个元素一个数组

代码实现

算法分析

时间复杂度

O(nlogn)

空间复杂度

O(n)

是否是原地排序

否

因为有个临时数组 tmp

是否是稳定排序

是

快速排序

原理

随机取数组中一个值，以它为中点，然后把数组比分为两部分，一部分比它大，一部分比它小

一般这个中点是数组中最后一个值，把比中点小的放左边

然后一直去重复这个操作，到最后把中点放到最后一个比它小的值后面

代码实现

算法分析

时间复杂度

最好情况：O(nlogn) 分区每次都平均分成2份

最坏情况：O(n^2) 中点极端，一个数组非常大，一个数组非常小

如 1，3，5，6，8

越有序，排序越慢

平均情况下：O(nlogn)

空间复杂度

O(logn)

是否是原地排序

是

是否是稳定排序

否

6，8，7，6，2，9，4

二分查找

原理

条件：有序数组

在数组中找一个中点，然后和对比值比较

如果中点比对比值大，则在前半部分查找

如果中点比对比值小，则在后半部分查找

一直到找到和对比值相等的元素，如果最后没找到，返回-1

代码实现

查找区间永远是闭区间[low,high] or [p,r]

循环条件永远是：low<=high or p<=r

对于 low==high 必要时特殊处理，在 while 内部补充退出条件，这条适用于某些变种问题

返回值永远是mid，而不是 low 、high

low、high 的更新永远是 low=mid+1和high=mid-1

对于非确定性查找，使用前后探测法，来确定搜索区间

先处理命中情况，再处理在左右半部分查找的情况

算法分析

时间复杂度

最好情况：O(1)

最坏情况：O(logn)

平均情况下：O(logn)

空间复杂度

O(1)

常用场景

二分查找适合数据量适中的数组去查询

二分查找的变形

查找第一个值等于给定值的元素

查找最后一个值等于给定值的元素

查找第一个大于等于给定值的元素

查找最后一个小于等于给定值的元素

寻找旋转排序数组中的给定值

[7,9,10,11,14,1,2,3,5,6]

问题拆分成：顺序区间，循环顺序区间

顺序区间检查办法，通过中点mid 和 low 来检查是否在顺序区间
如上面的数组，mid 为4，元素是14，那么在[low,mid]是顺序区间
这样程序将会简化处理顺序区间和非顺序区间

然后做对应的处理

如果target 在非顺序区间，那就在非顺序区间处理，target 最终是会落到顺序区间的

寻找旋转排序数组中的最小值

有重复数据的循环有序数组中查找给定值

查找峰值

思路：把数组分成山的两侧，一侧是左边，一侧是右边

然后命中目标的条件是 mid>mid-1 && mid > mid+1

在山的左侧找山顶时，mid>mid-1,low=mid+1

在山的右侧找山顶时，mid>mid+1,high=mid-1

二分答案

散列表/哈希表

原理

特殊存在

位图

原理

利用二进制位来表示，位图存的是范围，每次设置的都是位图的最大范围

分析

如有1千万的数据，数据是32位的整型数，存储需要大约40M（32位，1字节=8位，每个数据是4字节，1千万*4字节/1024/1024约等于40M）

使用位图，如果数字范围是在1到1亿之间，取最大值，1亿个二进制位，（1亿/8位/1024/1024约等于12M）

优点

大数据量节省内存（数据分布均匀）

无重复数据可以直接排序，时间复杂度为O(n)

缺点

如果数据的元素的范围特别大（数据分布不均匀），那么很消耗内存

元素不是整型的时候，不适用

比如1千万数据，数据为32位整数型，数字范围是1到10亿，那么取最大值，10个二进制位，（10亿/8位/1024/1024约等于120M）

代码实现

变量定义：num or value 是传参的值，index 是数组的下标，remainder 是余数, bit 是 bit 数组

index = num/8

remainder=num%8

增：bit[index] |= 1<< remainder

查：(bit[index] & (1<< remainder))!=0

删：bit[index] &^= 1<<remainder

布隆过滤器

基于位图实现，利用哈希冲突（设计多个哈希函数），减少存储空间带来的问题

原理

基于位图实现

实现多个hash函数，来分别计算元素应该存储在哪一位上

使用场景

不需要100%准确的，允许存在小概率误判的大规模判重场景

请求特别大的时候，查询数据库前，先查布隆过滤器，如果数据不存在，就不需要访问数据库，这样来减少数据库的操作

如某个数据是否存在数据库中，uv去重，防止缓存穿透等

优点

快速判重、节省内存，对位图的优化，属于CPU密集型

缺点

会误判，不适合高精的判重场景

特点

判定存在，有可能不存在

例如：3123和1123 哈希值相同，位图中存储了 3123，没有存储1123，那查询1123也会返回true

判定不存在，那肯定不存在（主要使用这个特点）

例如查询3123 返回false，那就3123不存在

代码实现

树

概念

根节点

没有父节点的结点是根节点

父节点

比如根节点，它有左右两个子节点，相对于子节点来说，他是两个子节点的父节点

子节点

父节点下的节点

兄弟节点

右子节点和左子节点可以互相叫为兄弟节点

叶子节点、叶节点

把没有子节点的节点叫叶子节点

节点的高度

节点到叶子节点的最长路径（边数）

节点的深度

根节点到这个节点所经历的边的个数

节点的层数

节点的深度+1

树的高度

根节点的高度

分类

二叉树

有两个叉的树，也就是两个子节点

左子节点和右子节点

满二叉树

概念

除了叶子节点外，其他的所有节点都有左右两个子节点

完全二叉树

概念

和满二叉树稍微有些不同，只要是最后一排子节点的叶子节点是顺序缺失的就是完全二叉树(除了最后一排子节点外，其他的子节点都是满的)

各个操作的性能

完全二叉树>平衡二叉树>近似平衡二叉树

维护平衡的成本

完全二叉树>平衡二叉树>近似平衡二叉树

在工程中使用红黑树，这种近似平衡二叉树的原因是，能降低维护平衡的成本，并且操作性能也不差

二叉树

分类

二叉树

有两个叉的树，也就是两个子节点

左子节点和右子节点

满二叉树

概念

除了叶子节点外，其他的所有节点都有左右两个子节点

完全二叉树

概念

和满二叉树稍微有些不同，只要是最后一排子节点的叶子节点是顺序缺失的就是完全二叉树(除了最后一排子节点外，其他的子节点都是满的)

分辨小技巧

分辨是不是完全二叉树还有一个小技巧，把二叉树的节点落在数组中

如果数组中间没有空洞，那就是完全二叉树

如果数组中间有空洞，那就不是完全二叉树

如[1,2,3,4,空,6,7,8] 这是不完全二叉树

如[1,2,3,4,5,6,7,8，空，空，空] 这是完全二叉树，这里的空说明是创建数组的时候多创建了，无所谓，不要即可

二叉搜索树

BST

平衡二叉树\VAL

二叉树图

图

二叉树图

存储方式

基于指针存储

代码

基于数组存储

只适合于完全二叉树、堆、线段树

存储方法(根存储在下标为1的位置)

根节点存储在下标为1的位置

左子节点位置为 2*i

右子节点位置为 2*i+1

父节点位置 i/2

存储方法2(根存储在下标为0的位置)

左子节点位置为 2*i+1

右子节点位置为 2*i+2

父节点位置 (i-1)/2

遍历方法

前序遍历

先当前节点，然后左子节点，然后右子节点

中序遍历

先左子节点，然后当前节点，然后右子节点

后序遍历

先左子节点，然后右子节点，然后当前节点

这里的前序，中序，后序说的就是当前节点在遍历中的位置，前序就第一个是当前节点，中序就当前节点在中间，后序就是当前节点在最后

三种遍历方法图

算法分析

时间复杂度

最优时间复杂度

log2^n次方

最坏时间复杂度

O(n) 二叉树成了一条线的链表

二叉搜索树\查找树

原理

一种特殊的二叉树，支持快速查找、插入、删除数据

在二叉树中的任意一个节点

左子树中的每个节点的值，都小于父节点的值

右子树中的没个节点的值，都大于父节点的值

如果出现反着来的，那么上面的条件也反过开

查找操作

如果比根节点小，从左子树查找

如果比根节点大，从右子树查找

代码实现

插入操作

要插入的数据比当前节点的值小，且当前节点左子树为空，直接把数据插入到左子节点的位置

如果左子树不为空，继续递归左子树，直到找到左子树为空的位置

右子树一样

代码实现

删除操作

第一种情况：被删除的节点没有子节点

直接把父节点中指向要删除节点的指针指向null即可

第二种情况：被删除的节点只有一个子节点

把父节点中指向要删除节点的指针，重新指向要删除节点的子节点即可

第三种情况：被删除的节点有两个子节点

找到这个节点的右子树中的“最小节点”或者左子树中的“最大节点”，把它替换到要删除的节点上

然后再删除掉这个“最小节点”或者“最大节点”

如果用“最小节点”，那么它肯定没有左子节点，所以，可以应对第一种和第二种情况来处理

如果用“最大节点”，那么它肯定没有右子节点，所以，也可以应对第一种和第二种情况来处理

代码实现

复杂度分析

二叉树的查找、插入、删除性能，跟书的高度成正比

时间复杂度位于 log2^n ~ h 之间

二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于log2^n情况

从而各个操作效率下降，极端情况下，二叉树退化为链表，时间复杂度退化为O(n)

平衡二叉查找树/AVL树

原理

任意一个节点的左右子树的高度相差不能大于1

近似的树

红黑树

时间复杂度

log2^n

堆

定义和存储

一、堆必须是一个完全二叉树

二、堆中的每个父节点的值必须大于等于(或者小于等于)左右子树中每个节点的值

大顶堆：堆中每个节点的值都大于等于其左右子树中每一个节点的值

小顶堆：堆中每个节点的值都小于等于其左右子树中每一个节点的值

存储：堆事完全二叉树，适用于数组来存储

计算父节点和子节点位置方法

以根节点为下标1的数组

左子节点位置 2*i

右子节点位置 2*i+1

父节点位置 i/2

以根节点为下标0的数组

左子节点位置 2*i+1

右子节点位置 2*i+2

父节点位置 (i-1)/2

操作

自上而下的操作

自下而上的操作

插入数据

操作方法：

先插入数据

然后自下而上的堆化

对比插入值和父节点的大小，如果堆是大顶堆，哪个值大哪个就在父节点，小的成为子节点

如果是小顶堆，把小的那个放到父节点

时间复杂度

最好情况 O(1) 插入之后不需要堆化

最坏情况 O(h) h是堆的高度

取堆顶元素

删除堆顶元素

操作方法：

先把最后一个节点替换到堆顶，然后删除原有堆顶

然后自上而下的堆化

判断左右子节点和父节点，三个中哪个最大，把大的交换到父节点

时间复杂度

最优时间复杂度O(1)

最坏时间复杂度O(h)

更新元素值

操作方法

更新之后的值变小了，进行自上而下的堆化

更新之后的值变大了，进行自下而上的堆化

堆排序

原理

基于堆

先建堆，把数组中的元素原地组织成一个堆

然后再基于堆进行排序

建堆

第一种方法

从前往后处理每个元素，对每个元素执行自下而上的堆化

时间复杂度O(nlogn)

第二种方法

从后往前处理每个元素，对每个元素执行自上而下的堆化

时间复杂度O(n)

排序

将堆顶元素与最后一个元素交换，最大元素就放到了下标n的位置，堆大小 -1

交换之后的堆顶元素，自上而下堆化，重新构建成堆

一直重复这个过程，直到最后堆中只剩下一个元素，排序工作就完成了

算法分析

是否是原地排序

是

是否是稳定排序

否

因为他会把元素重复的哪来放在堆顶

时间复杂度

O(nlogn)

空间复杂度

O(1)

字符串匹配

匹配过程，模式串和主串的匹配过程，模式串在主串中不停地往后滑动

BF算法

暴力算法

分为主串和模式串(就是短的那个匹配串)

让模式串在主串中一个一个的去对比，直到全部匹配

代码实现

RK算法掌握就好，不需要写

Rabin-Karp 算法

通过哈希算法对主串中的 n-m+1个子串分别求哈希值，然后逐个与模式串的哈希值比较

n代表主串的长度，m表示模式串的长度 n-m+1 是主串按照模式串的长度分割，主串的最后m个不能分割，视为1，所以主串能分割n-m+1个子串

哈希算法，普通的哈希算法太复杂，RK算法设计了一套利用当前子串来算出下一个子串的哈希算法

缺点：

模式串不能太长

RK的哈希算法思想：

比如主串，模式串是由26个字母组成

我们用26进制来做哈希算法

把子串的哈希值算出来，h[i]=s[i,i+m-1]哈希值（h是长度 n-m+1，i 是下标，i+m-1是第i个子串的尾部）

h[i+1]=s[i+1,i+m]的哈希值

比如 h[i] = "dfc"，那么h[i]的哈希函数为 ('d'-'a')*26^2+('f'-'a')*26^1+('c'-'a')*26^0

h[i+1]="fca",那么h[i]的哈希函数为 ('f'-'a')*26^2+('c'-'a')*26^1+('a'-'a')*26^0

h[i]的哈希公式为 (26^(m-1))*(s[i]-'a')+(26^(m-2))*(s[i+1]-'a')+...++(26^0)*(s[i+m-1]-'a')) 这里的s代表着字符串

h[i+1]的哈希公式为 (26^(m-1))*(s[i+1]-'a')+...+(26^(1))*(s[i+m-1]-'a')+(26^(0))*(s[i+m]-'a')

所以h[i+1]的哈希公式为 (h[i] - (26^(m-1))*(s[i]-'a'))*26+(26^(0))*(s[i+m]-'a')

哈希函数可以根据 h[i]返回 h[i+1]的哈希值

BF和RK的做法

遇到不匹配的字符时，讲模式串往后滑动一位，然后模式串的第一位开始重新匹配

BM和KMP算法

复杂度

最好情况下时间复杂度O(n/m)，n是主串的长度，m是模式串的长度

最坏情况下，O(n)

BM和KMP的做法

寻找某种规律，借助这种规律，当模式串和主串中的某个字符不匹配时，能够跳过一些肯定不会匹配的情况，将模式串往后多滑动几位

比如主串 abcacabdc,模式串 abd,当匹配到abc的时候，主串中的c和模式串中的d不匹配，那么模式串就直接挪到主串的c后面一位开始匹配

单模式串匹配

在字符串 abcdefg 中查找字符串 abc

多模式串匹配

在字符串 abcdefghijk 中查找字符串 abc，def，ijk

可以用 Trie树和 AC自动机，首选AC自动机

Trie树

适合前缀匹配

原理

Trie树是一颗多叉树，根节点不包含字符，其他每个节点表示字符串中的一个字符，从根节点到红色节点的一条路径表示字符串集合中的一个字符串

Trie树图

应用场景

字符串查找

完全匹配

代替方案：红黑树，散列表

多模式串匹配

优先使用AC自动机

前缀匹配

例如自动提示，搜索引擎、输入法、浏览器

回溯（重点）

是DFS和动态规划的基础

需要用到递归

解决穷举问题

核心思想

回溯的处理过程是一个穷举的过程。

枚举所有的解，找出其中满足期望的可行解

为了枚举所有可能的解，避免遗漏和重复，可以把问题求解的过程归纳为多阶段决策模型

每个阶段的决策会对应多个选择，从可选的选择列表中，任意选择一个，然后继续进行下一个阶段的决策

整个决策的过程，如果用图像形象话表示，就是一颗决策树

回溯穷举所有解来查找可行解的过程，就是在决策树中进行遍历的过程

遍历过程中记录的路径就是解

回溯一般使用递归来实现，递归树和决策树完全一样

递的过程进行函数调用，对应到递归树上为从一个节点进入它的子节点

归的过程进行函数调用返回，对应到递归树上是从子节点返回上一层节点

代码模板

源码

常见算法

全排列

思路：暴力遍历把元素拆分成树，类似于二叉树那样的遍历

源码

N皇后

思路：检查每一的每个位置能不能放皇后，直到找到能放皇后的位置为止

能放皇后的位置：在随意一个位置检查当前位置的整列，左上角对角线，右上角对角线，只要有任何一条线上有皇后，就不可以放皇后，否则就可以放

源码

0-1背包问题

思路：也是暴力遍历，只不过把是把总重量不超过规定重量的最大值即可

决策树就是装和不装两种关系

源码

数独问题

思路：和N皇后思路差不多，检查每一个要插入的位置的行，列，块（所在的小九宫格）是否有重复元素，没有就插入

不一样的地方，借助位图，来判断行，列，块里的位置有没有元素和查找重复元素

源码

子集问题

思路：把整个数组拆成决策树来遍历，那么就会出现两种情况，选与不选

源码

组合问题

和子集问题相思，不过是先把数转换成类似数组，然后进行决策树来遍历，选与不选

组合问题也是一种全排列问题

代码

图

应用：

微博、微信、Linkedln 等可以互加好友的

图的算法：图的搜索，最短路径、最小生成树、二分图等

什么是图

图是一种非线性表数据结构

图中的元素被称为“顶点”

图中的顶点可以和任意其它顶点建立连接关系，这种关系我们叫“边”

ABCDEF叫顶点，他们之间的线叫做边

无向图

无向图就是没有指向，他默认是双向的

有向图

定义

边带指向的图叫有向图

度

入度

有几条指向这个顶点的边就说明有几个入度

出度

这个顶点有几条边指向别的顶点就说明有几个出度

比如A有一个入度，2个出度

带权图

定义

每条边有一个“权重”

通过这个权重表示某种关系度，亲密度等

A，C 的边权重是5，这个图是个无向图

邻接矩阵存储方式

邻接矩阵

底层依赖一个二维数组

他把两个顶点组合成一个二维数组，比如1，3之间有边

无向图在二维数组中把[1,3]和[3,1]的位置上都标记为true

有向图（1出度，3入度）在二维数组中在[1,3]位置上为true，[3,1]位置上还是false

带权图（这里用无向图 1，3的边上权重是5）在二维数组中 [1,3]和[3,1]的位置上都标记为5

源码

邻接矩阵

邻接表

底层是一个链表加数组构成

数组的下标表示图的顶点，数组的链表表示了该顶点的指向顶点，有可能是一个，有可能是多个

邻接表有邻接表和逆邻接表

社交使用场景

邻接表

用来表示你关注了谁

逆邻接表

用来表示谁关注了你

源码

邻接表：1关注了2，2关注了3，5，4，逆邻接表：1被4关注了，2被1，4关注了

邻接表的优化

基础邻接表

链表构成

不适合快速判断两个用户间是否关注与被关注

优化版

使用跳表

支持快速查找，插入，删除

时间复杂度 O(logn)

空间复杂度 O(n)

跳表有序，分页获取粉丝列表或关系列表非常高效

可以通过 哈希算法 等数据分片方式，将邻接表存储在不同的机器上

或者利用外部存储，持久化到存储关系数据库，在表上建立多个索引

用邻接表存储在不同服务器

存储图的方式

邻接表（内存中存储，可以使用邻接表）

关系型数据库（图需要持久化就需要关系型数据库）

图数据库（超大图，并且设计大量图计算，用专业的图数据库）

图上常用的算法

搜索 or 遍历

BFS

DFS

最短路径

Dijkstra

针对有权图的单源最短路径算法，并且要求没有负权边

Bellman-Ford

针对有权图的单源最短路径算法，允许存在负权边

Floyd

针对有权图的多源最短路径算法，允许存在负权边，但不允许负权环

A*算法

启发式搜索算法，求有权图的次优最短路线

最小生成树

Prim 算法

Kruskal 算法

最大流、二分匹配

Ford-Fulkerson

Edmonds-Karp

DFS&BFS（深度和广度优先算法）搜索/遍历

BFS

Breadth-First Search 广度优先算法

树是图的一种特殊情况

二叉树的按层遍历，实际上就是广度优先搜索，先遍历与根节点近的，再逐层与根节点远的

图的广度优先搜索和树上的按层遍历很像，先查找离起始顶点最近的，然后是次近，依次往外搜索，直到找到终止顶点

思路：

二叉树广度优先遍历（层序遍历）使用的是队列，顶点的下一层是2*i和2*i+1

图的广度优先搜索也要用到队列

图的按层遍历，需要用一个 visited 数组，记录已经遍历过的顶点，这是为了防止图中存在环，出现循环遍历多次的情况

DFS

Depth-First-Search 深度优先算法

类似于树的递归，前中后序遍历

动态规划

解决穷举但是有重复子问题的

经典模型

背包问题（0-1、完全、多重、二维费用、分组、有依赖）

路径问题

打家劫舍&股票买卖

爬楼梯问题

匹配问题（LCS、编辑距离）

其它（LIS）

DP专题

适用问题

使用于可以用回溯解决，但是有重复字问题的

解题步骤

可用回溯解决

需要穷举搜索才能得到结果的问题

能用动归解决的问题都能用回溯解决

能用回溯解决的问题不一定能用动归解决

最值、可行、计数

构建多阶段决策模型

是否能将问题求解过程分为多个阶段

查看是否存在重复子问题

是否有多个路径到达同一状态

定义状态（难点）

如何记录每一阶段的不重复状态

二维费用背包

int dp[n][w+1]记录每一阶段可达的所有状态

dp[i][j]表示第 i 个物品决策完之后，存在背包中物品重量为 j ，对应的最大物品价值

定义状态转移方程（难点）

找到如何通过上一阶段的状态推导出下一阶段的状态

二维费用背包

确定第 i 阶段的(i,j)这个状态，如何通过上一阶段i-1的哪些状态转移过来(i,j)这个状态只有可能由(i-1,j)和(i-1,j-weight[i])转换过来

dp[i][j]=math.Max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

画状态转移表

辅助理解，验证正确性，确定状态转移的初始值

动态规划代码

0-1背包问题

问题：对于一组不同重量的物品，选择其中一些物品装入背包，在不超过背包最大重量限制的前提下，背包中可装物品总重量的最大值是多少？

1、可以用回溯解决，穷举问题

2、构建多阶段决策模型：每一阶段决策一个物品是否放入背包

3、查看是否存在重复子问题：某一阶段背包中物品重量为cw，可以通过不同路径到达

4、定义状态：var dp[n][w+1] bool 记录每一阶段可达的所有状态
dp[i][j]=true 表示第i个物品决策完之后，存在背包中物品重量为j这种状态

5、定义状态转移方程：

确定第 i 阶段的(i,j)这个状态，如何通过上一个阶段 i-1 的哪些状态来转移过来

(i,j)这个状态只有可能由(i-1,j)和(i-1,j-weight[i])转移过来

dp[i][j]=dp[i-1][j]||dp[i-1][j-weight[i]]

6、画状态转移表：辅助理解，验证正确性，确定状态转移的初始值

7、写代码

二维费用背包问题

问题：对于一组不同重量、不同价值的物品，选择其中某些物品装入背包，不超过背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少？

1、可以用回溯解决，穷举问题

2、构建多阶段决策模型：每一阶段决策一个物品是否放入背包

3、查看是否存在重复子问题：某一阶段背包中物品重量为cw，可以通过不同路径到达

4、定义状态：var dp[n][w+1] bool 记录每一阶段可达的所有状态
dp[i][j]=true 表示第i个物品决策完之后，存在背包中物品重量为j这种状态

5、定义状态转移方程：

确定第 i 阶段的(i,j)这个状态，如何通过上一阶段i-1的哪些状态转移过来

(i,j)这个状态只有可能由(i-1,j)和(i-1,j-weight[i])来转移过来

dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]+value[i])，weight 是物品重量数组，value 是物品价值数组

6、画状态转移表：辅助理解，验证正确性，确定状态转移的初始值

7、写代码

最值

问题：有N个物品，选择其中一些物品装入背包，在不超过背包最大重量限制的前提下，背包中可装物品总重量的最大值是多少？

状态：

var dp [n][w+1]bool 记录每阶段可达状态

dp[i][j]=true 表示第 i 个物品决策完之后背包重量为 j 这个状态可达

状态转移方程：

(i,j)这个状态只有可能(i-1,j)和(i-1,j-weight[i])两个状态转移过来的

dp[i][j]=dp[i-1][j] || dp[i-1][j-weight[i]]

最值

问题：有n个物品，选择其中一些物品装入背包，正好装满背包所需物品的最少个数？（如果装不满，返回-1）

状态：

var dp[n][w+1] int 记录每个阶段可达状态，就是记录每个阶段最少物品个数

dp[i][j] 表示第 i 个物品决策完，重量为 j ，对应的最少物品个数

状态转移方程：

(i,j) 这个状态只有可能从(i-1,j)和(i-1,j-weight[i]) 两个状态转移过来

dp[i][j]=min(dp[i-1][j],dp[i-1][j-weight[i]]+1)

可行

问题：有n个物品，选择其中一些物品装入背包，能不能正好装满背包？

状态：

var dp [n][w+1]bool 记录每阶段可达状态

dp[i][j]=true 表示第 i 个物品决策完之后背包重量为 j 这个状态可达

状态转移方程：

(i,j) 这个状态只有可能从(i-1,j)和(i-1,j-weight[i]) 两个状态转移过来

dp[i][j]=dp[i-1][j] || dp[i-1][j-weight[i]]

计数

问题：有n个物品，选择其中一些物品装入背包，装满背包有多少种不同的装法？

状态：

var dp [n][w+1]int 记录每阶段可达重量对应的装法个数

dp[i][j]表示第 i 次决策完之后，背包重量为j，对应有几中装法

状态转移方程

(i,j) 这个状态只有可能从(i-1,j)和(i-1,j-weight[i]) 两个状态转移过来

dp[i][j]=dp[i-1][j]+dp[i-1][j-weight[i]]

空间优化

使用二维的滚动数组来替代dp数组

只使用一维数组来代替二维数组

数据结构

线性结构

数组

链表

栈

队列

非线性结构

树

图

堆

算法

排序算法

冒泡排序

选择排序

插入排序

快速排序

查找算法

顺序查找

二分查找

哈希查找