工作准备-03（dfs、dp、贪心算法总结）

迷南。 2022-08-29 05:56 211阅读 0赞

# 算法经验总结篇 #

## 深度优先遍历（dfs） ##

对于遍历算法来说，dfs经常会用到，且频率也比bfs高得多，下面总结一下目前做题之后对于dfs所想所感：  
dfs一般思路如下：  
1. 明确下一遍历子状态是什么样的  
2. 题解的条件是什么  
3. 是否需要剪枝，需要的话那么剪枝的条件又是什么（一般是去重操作，去重操作一般解法：  
a. 先排序后判断重复情况是什么，并去除重复解  
b. 用一个数组进行标记，将用过的元素标记，下次再取的时候先判断元素是否用过再决定用不用此元素。）

dfs其实就是一种递归，里面也包含回溯，就像开一扇窗，里面又有一扇窗再开，里面又有一扇，又开…如此不断开窗，直到打开最后一扇窗里面不是窗户，而是一堵墙（题解的条件），再一层一层从最里层的窗户开始关闭，最后退回到第一扇窗户，之后返回所有在此退回状态中得到的解。（自我形象比较，看不懂就当我没说…）。  
从上面看，dfs就像栈的特性一样，你觉得呢？？？

## 动规（dp） ##

看到什么就要想到dp呢？？  
如果题目中意思表达为：  
**1. 当前最优解是子问题最优解得到的，（这和贪婪有区别，贪婪是直接取当前最优解），动规是根据子问题推导当前结果  
2. 统计数量  
3. 子问题的解与后面问题的解无关**  
**动规的解题思路：**  
a. 确定动规数组的含义以及动规数组下标的意义  
b. 确定动规状态方程  
c. 根据动规状态方程初始化动规数组  
d. 确定遍历顺序  
e. 举例推导动规数组值  
（以上这几点是代码随想录里面归纳总结的方法论，个人感觉还是挺不错的）  
**动规的一般出错检查思路：**  
首先看看动规数组是否是自己所想的那样的结果，如果是的话，则再看看是不是自己动态规划方程有问题或者初始化有问题或者遍历的顺序有问题。  
**动态规划优化:**  
动态规划的优化指的是在空间复杂度上的优化，一般我们需要存储动态规划中每一步的结果，之后通过搜索存储的结果输出解，这样耗费太多的空间。**优化：** 创建几个变量，分别用来保存最近一次运算的结果和所用到的中间值，在当前运算结束之后，更新这几个变量的值，为下一次运算提供中间变量。

以上是目前的刷题总结，之后还会更新…

**------------补充-------------**

### 背包问题总结： ###

#### 01背包： ####

***特征***：每个物品仅能够挑选一次，每个物品数量为1  
**基本框架：**  
//**二维dp数组**  
//遍历顺序：先遍历物品后遍历背包或者先遍历背包后遍历物品都是可以的  
//以下举例先遍历物品后遍历背包情况  
//初始化的时候需要把第一行中的所有元素均初始化和第一列中的元素也要初始化

for(int ix = 1; ix < weight.size(); ++ix){ 
    	for(int iy = 0; iy <= bagsize; ++iy){ 
    		if(iy < weight[ix]){ 
    			dp[ix][iy] = dp[ix - 1][iy];
    		}else{ 
    			dp[ix][iy] = max(dp[ix - 1][iy], dp[ix - 1][iy - weight[ix]] + value[ix]);
    		}	
    	}
    }

//**一维dp数组**  
//遍历顺序：先遍历物品后遍历背包不能够将遍历顺序倒过来，即不能先遍历背包后遍历物品：如果这样的话，那么就会出现每个背包容量中只放了一个物品  
一维dp数组与二维dp数组两点不同：  
//1.先遍历物品后遍历背包–>不会使每个容量的背包只添加了一个物品  
//2.要记住对于背包遍历那一层需要倒序遍历–>不会让有重复添加物品的情况出现

for(int ix = 0; ix < weight.size(); ++ix){ 
    	for(int iy = bagsize(); iy >= 0; --iy){ 
    		if(iy >= weight[ix]){ 
    			dp[iy] = max(dp[iy], dp[iy - weight[ix]] + value[ix]);
    		}	
    	}
    }

#### 完全背包： ####

***特征***：每个物品可以选择无数次（这是与01背包唯一不同的地方）  
***基本框架***  
其实完全背包和01背包唯一的不同点就是在对于背包遍历的方式，01背包遍历背包的时候需要倒序遍历（为了不让元素重复添加），但是完全背包在遍历背包的时候是按顺序遍历的，也就是从0到背包的最大容量，因为他可以重复添加元素。  
//**一维数组**  
//遍历顺序：先遍历物品，后遍历背包，（或者先遍历背包，后遍历物品）  
//以下是先遍历物品，后遍历背包

for(int ix = 0; ix < weight.size(); ++ix){ 
    	for(int iy = weight[ix]; iy <= bagsize; ++iy){ 
    		  dp[iy] = max(dp[iy], dp[iy - weight[ix]] + value[ix]);	
    	}
    }

//先遍历背包，后遍历物品

for(int iy = 0; iy <= bagsize; ++iy){ 
    	for(int ix = 0; ix < weight.size(); ++ix){ 
    		 if(iy >= weight[ix]){ 
    		     dp[iy] = max(dp[iy], dp[iy - weight[ix]] + value[ix]);
    		  }
    	}
    }

为什么在完全背包中一维dp数组的遍历顺序中先遍历物品后遍历背包和先遍历背包后遍历物品都是一样的呢？  
答：因为完全背包在一维dp数组中对背包的遍历是从小到大遍历的，而根据递推公式可以得到，如果要计算得到当前的值时需要知道之前的值，因为从小到大遍历使得之前的值都已经计算好了，所以这两种遍历顺序都可以。

为什么在01背包中二维dp数组遍历顺序中先遍历物品后遍历背包和先遍历背包后遍历物品都是一样的呢？  
答：  
先遍历物品后遍历背包：从递归公式上就可以看出，当前所计算的dp值与上一行dp值有关，而我们先遍历物品的，即行遍历，所以上面的行中的值我们已经计算出来了（第一行都初始化了），所以当前值可以直接由其得出。  
先遍历背包后遍历物品：从递推公式上我们可以看出，计算当前dp值需要正上方dp值与正左上方dp值，而我们先遍历背包，即列遍历，所以正上方的dp值和正左上方的dp值我们已经计算出来了（第一列初始化了），所以当前值可以之间由其得出。

#### 问题类型小结： ####

##### 1.正常的背包问题 #####

*公式：dp\[j\] = max(dp\[j\], dp\[j - weight\[i\]\] + value\[i\]);*  
即纯01背包问题或者完全背包问题的应用。  
这种应用问题一般会将物品的重量和价值看成一个值来进行计算。  
而且这种问题一般会隐藏”背包容量”，所以我们需要将背包容量抽象出来。

##### 2.组合和排列： #####

*公式：dp\[j\] += dp\[j - weight\[i\]\];*  
**组合问题**：先遍历物品，后遍历背包—>按照物品先遍历的原则，其中元素相同，顺序不同只能算一种组合，所以按物品先遍历不会出现相同元素不同组合  
**排列问题**：先遍历背包，后遍历物品—>相同元素不同顺序算不同的排列，先遍历背包，在遍历物品可以在每次背包装载的时候都进行一次物品的全选择，这样就可以构造相同元素不同顺序的不同排列。

1.  排列、组合问题在01背包中重点就是公式：dp\[j\] += dp\[j - weight\[i\]\];
2.  排列、组合问题在完全背包一维数组中重点需要关心的是遍历的顺序问题。即以上所示的遍历顺序。

##### 3.路径中所用元素个数最少或者最多 #####

*公式：dp\[j\] = min/max(dp\[j\], dp\[j - weight\[i\]\] + 1)*  
这类问题需要关心初始化dp元素。  
**最少**：当物品的价值全为正数时，非0下标的元素全部初始化为INT\_MAX  
**最多**：当物品价值全为正数时，非0下标的元素全部初始化为0；如果物品的价值有负数时需要将非0下标的元素初始化为INT\_MIN。

*递推公式小结：*  
**求总和问题**：一般求总和问题，例如求排列的总和或者组合的总和，例如兑换零钱中，target能够兑换零钱的方法总共有多少种（装满背包有多少种）：递推公式一般为---->dp\[j\] += dp\[j - weight\[i\]\];  
**求路径个数**：比如求兑换零钱中，能够将target兑换成最少/最大的零钱个数为：dp\[j\] = min/max(dp\[j\], dp\[j - weight\[i\]\] + 1);//意思是不进行当前零钱兑换，或者兑换当前零钱所用到的零钱个数。

*最后总结一下代码随想录同志总结出来的动规五部曲：*  
1. 定义dp数组，明确dp数组的下标和dp数组值所代表的含义。—>一般都是所给的”背包容量作为下标“，所要求的值作为dp数组值的含义。  
2. 确定动态规划转移方程—>一般就是那几种方式，记住即可。  
3. 根据动态规划转移方程初始化dp数组—>初始化的时候要注意：当求max时且所给物品值没有负数的时候可以初始化dp下标非0元素为0，如果物品值中有负数的话需要初始化为最小值，即INT\_MIN；如果求min时dp中非0下标元素需要初始化为INT\_MAX。  
4. 确定遍历顺序—>看求的是排列还是组合或者其他，排列–先遍历背包后遍历物品，组合–先遍历物品后遍历背包。其他可以据情况而定。  
5. 举例查看dp数组是否按照正确的结果导出—>如果没有按照正确的结果导出，需要检查一下是否初始化、遍历顺序、动态规划方程有问题。  
**总结**：动态规划又名记忆化搜索，他是根据子状态（之前状态）来推断出当前状态，所以当求一个当前值的时候，我们要从最初值一步一步求到当前值，这样才能保证当前值最优。  
对以上五部曲有自己的心得：  
1. dp数组所表示的值一般是需要求解的答案，而dp数组的下标一般为影响求值的最少因素（可以包含全部因素）。**补充：** **需要根据实际写出dp所有可能的情况，按照可能的情况再去看每种情况能够如何得到，即每种情况的递推公式：如最经典的股票买卖问题。**  
2. dp转换公式一般是根据之前的值来确定当前的dp值，也就是能够得到dp值的计算公式（需要包含所有能够得到dp值的方法，但是需要从中得到题目要求（最少，最大，最多，最小…））。  
3. 根据dp的动态转移公式进行判断需要初始化哪些元素（一般dp\[0\]需要初始化，即下标为0的需要初始化），需要初始化成哪些元素，需要根据dp数组具体的含义进行定夺。  
4. 根据dp的动态转移公式进行判断当前dp值的求取是通过怎样的方式来的，也就是通过什么样的路径（体现在dp数组中就是从上到下或者从左到右…）来求得当前的dp数组的值。  
5. 我们可以设置几个参数来进行求解，一步一步推导dp数组，看dp数组中的值是否是我们所期待的那样。如果不是，有可能是递推公式有问题，或者是dp数组初始化有问题，或者是遍历顺序有问题。

**补充：动态规划数组根据题目总结动态规划方程**

1.  常见的像计算结果的所有可能的个数，如：给你一定的总金额， 让你兑换成零钱，计算有多少种兑换方法，常使用以下动态规划方程：  
    dp\[i\] += dp\[i - weight\[i\]\];  
    leetcode中实例：377、494、377、70…
2.  常见的像计算达到目的时所用的最少路径，如：给你一定的总金额，让你兑换成零钱，计算兑换的零钱个数最少需要多少能达到最大金额，常使用以下动态规划方程：  
    dp\[i\] = min(dp\[i\], dp\[i - weight\[i\]\] + 1);  
    leetcode中实例：322、279  
    注：这种题目一般考察对dp数组的初始化，详细初始化方法见上面总结。
3.

## 贪心算法 ##

拿到一个算法题，如何知道这道题是否能够用贪心算法进行解？可以从以下方面进行考虑：

1.  首先思考能不能将问题分为很多子问题。
2.  思考能否找到子问题的最优解（局部最优解）。
3.  能够通过子问题的最优解得到全局问题的最优解。
4.  思考能够通过数学归纳法进行验证，或者通过反证法进行验证。  
    如果能够满足以上四点，则可以使用贪心算法，否则就是简单的模拟问题。