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

1、四种方法的对比

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;
}