LeeCode——回溯法、动态规划、贪心法、分治法（快速说明）

逃离我推掉我的手 2024-03-16 11:03 59阅读 0赞

## **1、四种方法的对比** ##

<table> 
 <thead> 
 <tr> 
 <th style="width:95px;">算法方法</th> 
 <th style="width:125px;">用处</th> 
 <th>优点</th> 
 <th>缺点</th> 
 <th>拓展与改良</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="width:95px;">回溯法</td> 
 <td style="width:125px;">适用于求解组合问题、排列问题、搜索问题等。</td> 
 <td> 1. 可以搜索整个解空间，找到最优解。 2. 不需要预先知道问题的解可能在哪里。 </td> 
 <td> 1. 时间复杂度高，因为需要遍历整个解空间。 2. 需要较大的空间存储搜索轨迹。 </td> 
 <td> 1. 剪枝优化。 2. 双向搜索。 </td> 
 </tr> 
 <tr> 
 <td style="width:95px;">动态规划</td> 
 <td style="width:125px;">适用于求解具有最优子结构的问题。</td> 
 <td> 1. 重复计算较少，效率高。 2. 可以通过将问题划分为多个子问题来简化问题。 </td> 
 <td> 1. 需要存储中间结果，占用空间较大。 2. 不能很好地处理某些非最优子结构的问题。 </td> 
 <td> 1. 记忆化搜索。 2. 状态压缩。 </td> 
 </tr> 
 <tr> 
 <td style="width:95px;">贪心法</td> 
 <td style="width:125px;">适用于求解具有贪心选择性质的问题。</td> 
 <td> 1. 算法简单，易于实现。 2. 通常时间效率较高。 </td> 
 <td> 1. 得到的不一定是最优解，很难证明其正确性。 2. 对于某些问题，可能无法使用贪心策略。 </td> 
 <td> 1. 局部搜索等启发式方法。 2. 迭代深化策略。 </td> 
 </tr> 
 <tr> 
 <td style="width:95px;">分治法</td> 
 <td style="width:125px;">适用于将一个大问题划分为多个相似子问题的情况。</td> 
 <td> 1. 对于一些规模较大的问题，可以减少问题的复杂度。 2. 可以利用并行计算提高效率。 </td> 
 <td> 1. 划分子问题需要一定的技巧和经验。 2. 对于一些问题，划分子问题比较困难。 </td> 
 <td> 1. 增加唯一性条件来避免重复计算。 2. 引入随机化算法增加多样性。 </td> 
 </tr> 
 </tbody> 
</table>

--------------------

### **2、一句话理解四种算法思想（知乎大佬总结的）** ###

> **`分治：分而治之，先解决子问题，再将子问题的解合并求出原问题。`**
> 
> **`贪心：一条路走到黑，选择当下局部最优的路线，没有后悔药。`**
> 
> **`回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。`**
> 
> **`动态规划：上帝视角，手握无数平行宇宙的历史存档，同时发展出无数个未来。`**

> --------------------
> 
> ### **回溯算法 Backtracking** ###
> 
> **通常用于求解组合问题、排列问题、搜索问题等，其优点在于可以搜索整个解空间，找到最优解，但缺点则是时间复杂度高，存储搜索轨迹需要较大空间。对回溯法可以通过剪枝优化、双向搜索等方式进行改良。**
> 
> ### **动态规划 Dynamic Programming** ###
> 
> **适用于求解具有最优子结构的问题，其优点在于重复计算较少，效率高，可以通过将问题划分为多个子问题来简化问题，但缺点则是需要存储中间结果，占用空间较大，不能很好地处理某些非最优子结构的问题。对动态规划可以通过记忆化搜索、状态压缩等方式进行改良。**
> 
> ### **贪心算法 Greedy** ###
> 
> **适用于具有贪心选择性质的问题，其优点在于算法简单易于实现，通常时间效率较高，但其缺点在于得到的不一定是最优解，难以证明其正确性，对于某些问题也无法使用贪心策略。对贪心法可以通过局部搜索等启发式方法、迭代深化策略等方式进行改良。**
> 
> ### **分治算法 Divide and Conquer** ###
> 
> **适用于将一个大问题划分为多个相似子问题的情况，其优点包括对于一些规模较大的问题可以减少问题的复杂度，可以利用并行计算提高效率，但其缺点在于划分子问题需要一定的技巧和经验，对于一些问题，划分子问题也比较困难。对分治法可以通过增加唯一性条件来避免重复计算、引入随机化算法等方式进行改良。**
> 
> --------------------

## **分治法应用** ##

> **在计算机算法中，回溯法是一种常见的算法思想，通常用于解决组合问题、排列问题、搜索问题等。回溯法的基本思路是：从问题的子集或解空间开始，逐渐向下一步扩展，直到找到问题的解，或者无解时回溯到上一步继续搜索。**
> 
> **除了 n 皇后问题外，回溯法还有许多其他应用问题，如：**
> 
> 1.  **组合总和问题：给定一个正整数数组 candidates 和一个正整数 target，找出 candidates 中所有可以使数字和等于 target 的唯一组合。这个问题可以通过回溯法的思想来解决。**
> 2.  **全排列问题：给定一个包含不同整数的数组 nums，返回其所有可能的全排列。这个问题也可以通过回溯法来解决。**
> 3.  **单词搜索问题：给定一个 m × n 的二维字符网格和一个字符串 word，如果 word 存在于网格中，则返回 true；否则，返回 false。单词搜索问题也可以通过回溯法来解决。**
> 4.  **八皇后问题：在 8×8 的国际象棋棋盘中放置 8 个皇后，使它们互相攻击不了。这也是一个著名的回溯法应用问题。**
> 
> **总之，回溯法是一种常见的算法思想，适用于许多组合、排列和搜索问题。在实际应用中，我们可以根据具体问题的特点和要求，选择合适的回溯法算法来解决。**

--------------------

## **01背包（动态规划）** ##

#include <stdio.h>
 #include <math.h>
 
 #define N 6 // 背包空间
 
 // 物品
 #define W 4 // 物品数量
 int value[] = {7,3,5,2}; // 价值
 int weight[] = {1,2,5,4}; // 重量
 
 // 数组记录
 int count[W+1][N+1] = {};
 
 int main(){
 
 int t,f; // 两个for循环
 // 数组初始化
 for(t=0; t<W+1; t++){
 for(f=0; f<N+1; f++){
 count[t][f] =0;
 }
 }
 
 int i,j; // 两个for循环
 for(i=1; i<W+1; i++){ // 遍历所有物品
 int nowWeight = weight[i-1]; // 当前物品的重量
 int nowValue = value[i-1]; // 当前价值
 for(j=1; j<N+1; j++){ // 遍历从 1 - 10重量的情况
 // 如果可以加上当前物品——并且——加上后的价值大于之前记录的价值，则更新——不行则记录之前的！
 if(nowWeight<=j && nowValue + count[i-1][j-nowWeight] > count[i-1][j]){
 count[i][j] = nowValue + count[i-1][j-nowWeight];
 }else{
 count[i][j] = count[i-1][j];
 }
 }
 }
 
 int n,m; // 两个for循环
 // 打印结果
 for(n=0; n<W+1; n++){
 for(m=0; m<N+1; m++){
 printf("%d ",count[n][m]);
 }
 printf("\n");
 }
 
 return 0;
 }

## **N皇后（回溯法）** ##

> **递归方法：**
> 
> #include <stdio.h>
> #include <math.h>
> 
> #define N 4
> int q[N+1]; // 数组里面存储的是——皇后所在的列号 [i,j] j = q[i] j列号 i行号（第i个皇后）
> int answer = 0; // 方案数
> 
> int queenCheck(int j){ // 行号
> int i = 0;
> for(i=0;i < j; i++){ // 循环判断 前面的所有皇后
> if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){ // 是否在同一列 || 是否在同一个斜线上
> return 0; // 不合法
> }
> }
> return 1; // 合法
> }
> 
> void queenInit(){
> int i;
> for(i=0; i<=N; i++){
> q[i] = 0;
> }
> }
> 
> void printAnswer(){
> int i;
> printf("plan %d:",answer);
> for(i=0; i<=N; i++){
> printf("%d ",q[i]);
> }
> printf("\n");
> }
> 
> void queenFunc(int j){ // 从第j个皇后开始
> int i;
> for(i=1;i<=N;i++){
> q[j] = i; // 位置不断往后挪
> //如果合法
> if(queenCheck(j)){
> if(j == N){ // 找到了 N皇后的一组解
> answer++;
> printAnswer(); // 打印方案
> }else{
> queenFunc(j+1); // 下一个皇后
> }
> }
> }
> }
> 
> int main(){
> queenInit(); // 初始化Queen
> queenFunc(1); // 执行
> 
> return 0;
> }
> 
> --------------------
> 
> **迭代方法：**
> 
> #include <stdio.h>
> #include <math.h>
> 
> #define N 8
> int q[N+1]; // 数组里面存储的是——皇后所在的列号 [i,j] j = q[i] j列号 i行号（第i个皇后）
> 
> int queenCheck(int j){ // 行号
> int i = 0;
> for(i=0;i < j; i++){ // 循环判断 前面的所有皇后
> if(q[i] == q[j] || abs(j-i) == abs(q[j]-q[i])){ // 是否在同一列 || 是否在同一个斜线上
> return 0; // 不合法
> }
> }
> return 1; // 合法
> }
> 
> void queenInit(){
> int i;
> for(i=0; i<=N; i++){
> q[i] = 0;
> }
> }
> void printAnswer(int answer){
> int i=0;
> printf("plan %d:",answer);
> for(i=0; i<=N; i++){
> printf("%d ",q[i]);
> }
> printf("\n");
> }
> 
> void queenFunc(){
> int answer = 0; // 方案数
> 
> int j = 1; // 从第一个皇后开始
> 
> while (j>=1){
> q[j] =q[j] + 1; // 从1开始，方便比较
> while (!queenCheck(j) && q[j]<=N){ // 不合法 && 位置没有超出
> q[j] +=1; // 往后挪
> }
> 
> if(q[j]<=N){ // 找到了合法位置
> 
> if(j == N){ // 找到了 N皇后的一组解
> answer++;
> printAnswer(answer); // 打印方案
> }else{
> j++; // 下一个皇后
> }
> 
> }else{ // 溢出了也没有找到——回溯！！
> q[j] = 0; // 把失败的皇后位置重置
> j--; // 回溯 ---如果一直回溯到之前的第一行皇后 ---此时皇后位置也越界了————那么说明——已经把全部的方案都走完了！
> }
> }
> printf("all plans: %d",answer);
> 
> }
> 
> int main(){
> queenInit(); // 初始化Queen
> queenFunc(); // 执行
> 
> return 0;
> }