注意事项

• 组合不强调元素之间的顺序，排列强调元素之间的顺序。

• 优先队列：即堆，该种数据结构可以在数据插入或者删除时随时获取已有数据的最大值或者最小值

• 哈希值比较少、特别分散、跨度非常大，使用数组代替map时就造成空间的极大浪费。

背包问题

0-1背包

用二维数组则是：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

dp[i][j]表示当背包重量为j时，从0-i任意去物品的最大价值

多重背包问题

其实多重背包问题，就是0-1背包问题的变种,把多个背包展开就行了

完全背包问题

基数排序

基数排序的思想是先对个位数进行排序，然后对十位数进行排序，最后对百位数进行排序。整体思想上是使用了桶的思想。

基数排序详解

性能测试：排序一亿个0-10,000,000范围内的无序随机数耗时：1m19.086580031s

• 虽然基数排序性能比较稳定，但是由于基数越大（最大数的位数）也就意味着可能有更多的空间被浪费

• 算法实现：

将一个数组划分为k份，每分和相同

此类的题型「采用状态压缩dp解决」

对应题目：

698. 划分为k个相等的子集

473. 火柴拼正方形

698. 划分为k个相等的子集

难度中等651
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
示例 2:

• 状态压缩解法

最短路径算法

Dijkstra算法是一种经典的基于贪心的单源最短路径算法，其要求图中的边全部非负弗洛伊德算法：是一种基于动态规划的多源最短路径算法

• 图



图矩阵图初始化：

弗洛伊德算法

弗洛伊德算法就是一个简单的动态规划问题，dp[i] [j]表示从i到j到最短路径花费，假如存在中间节点k使得dp[i] [j]<dp[i] [k]+dp[k] [j],则更新i到j到最短路径

• 利用path[i] [j]记录下每次i到j的中间节点k 上述例子最后得到的path如下：
• 则求0到4的最短路径的步骤为：
1. 查询path得到：0…3…4
2. 因为path[0] [3]==-1，所以0 3…4
3. 因为path[3] [4]==2，所以0 3..2..4
4. 因为path[3] [2]==-1和path[2] [4]==-1，所以最终路径为0 3 2 4

Dijkstra算法

如果start==0，则Dijkstra算法则会求出start到其他所有节点的最短路径。

如最后得到的paht：

• 如求0到4的最短路径：
因为dp[0] [4]=2所以到达4的前一个点为2，又因为dp[0] [2]=3，所以到达2的前一个节点为3，又因为dp[0] [3]=-1,所以0直接到达3。所以0到4的最短路径为： 0 3 2 4

随机化

• 有一个m*n的矩阵，随机生成有k个地雷的矩阵扫雷图

参考：生成一个扫雷矩阵

• 扫雷图介绍： 矩阵中如果是地雷则其值为-1，若不是其值则代表其周围的8个位置一共拥有多少个地雷

• 实现思路：
1. 该中题目相当于从mn个数中等概率取出k个数，每个数被取到的概率是k/n，我们将m n个矩阵转化为1维数组，每个位置存放其对应的一维下标，
last指针记录最后一个位置初始值为m * n
2. rand.Intn(last)从[0,last)中随机取一个位置，将该位置值和last对应位置的值交换，last–，k–，不断重复步骤2，直到k=0
3. 最后last及前面的所有位置都记录着矩阵中要生成地雷的位置

可以用蓄水池抽样解决的

• 一次性取k个相当于每次取1个一个取k次「有一次性取k个多蓄水池抽样，但是无法理解。。」，每次都[0,last)中进行蓄水池抽样就可以随机获取k个位置「即第二步，把rand.Intn(last)换成蓄水池抽样」

• 从n个数中等概率取1数「蓄水池抽样法」