首先，我是备考2023年上半年的考试。

一、历年考试题

        历年的考题如下，从表中分析可以看出，动态规划法、排序算法、回溯法、分治法是很大概率考察的算法，尤其是动态规划法，本身其理解难度较高，且可以出的题型很多。

        我猜测，2023年上半年很有可能就是出动态规划法。其次就是回溯法和分治法。回溯法学习n皇后问题就行了。

年份	考点
2022下半年	堆排序算法--时间复杂度计算--排序结果推导
2022上半年	动态规划算法（矩阵乘法）--时间复杂度计算--算法结果推导
2021下半年	动态规划算法--时间复杂度计算--算法结果推导
2021上半年	动态规划算法--时间复杂度计算--空间复杂度计算
2020下半年	希尔排序--时间复杂度/是否稳定--算法结果推导
2020上半年	（疫情原因取消）
2019下半年	动态规划算法（0-1背包问题） --自底向上或自顶向下 --算法结果推导
2019上半年	回溯法（n皇后问题）--算法结果推导
2018下半年	动态规划算法--时间复杂度计算--算法结果推导
2018上半年	动态规划算法/递归算法--时间复杂度计算
2017下半年	回溯法
2017上半年	分治法--时间复杂度计算--算法结果推导
2016下半年	KMP算法--时间复杂度计算--算法结果推导
2016上半年	动态规划算法--时间复杂度计算--算法结果推导
2015下半年	动态规划算法--时间复杂度计算--算法结果推导
2015上半年	回溯法（n皇后问题）--算法结果推导
2014下半年	动态规划算法--时间复杂度计算--算法结果推导
2014上半年	分治法--时间复杂度计算--算法结果推导

        其他博主总结的考点如下，参考看看就行了。

二、动态规划法

2.1 算法介绍

2.2 题型1：

三、回溯法（n皇后问题）

3.1问题描述

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题，即在n×n的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上。 

简而言之：n×n的棋盘上摆放n个皇后，不能同行，不能同列，也不能同斜线。

3.2回溯解法

首先这是一个排列组合问题，解空间的大小为：n!（n的阶乘）

如下图所示是解空间的构成树，又称排列树。

 解法一：如果硬去罗列所有排列组合，然后进行判断。规模稍大就不行了，因为是n!的问题规模。

解法二：采用回溯法，对排列树进行搜索，在中途就发现不行时，直接退出该路线，回溯到上一步，相当于在剪枝。

举个例子：

4皇后问题：

先将第一个皇后放在第一行的第一列上，符合题目要求

开始放置第二个皇后。放在第二行的第一个与第一行的皇后为同一列，不符合题意，继续向后搜素，放在第二列上面与第一个皇后在同一斜线上，不符合题意，继续向后搜素，发现放在第三列符合题意

开始放置第三个皇后。放在第三行的任意位置都会出现冲突，此时需要回溯，将第二个皇后放置在第四列，此时符合题意，继续放置第三个皇后，发现第三个皇后放置在第三行的第二列符合题意

继续放置第四个皇后。放在第四行的任意位置都会出现冲突，此时需要回溯，第三个皇后向后移动，发现依然不符合题意，继续回溯，第二行的皇后无法再向后移动，继续回溯，将第一个皇后向后移动到第二列，符合题意

移动第二个皇后，发现放在第四列符合题意

移动第三个皇后，发现放在第一列符合题意

移动第四个皇后，发现放在第三列符合题意

回溯结束

3.3源码

3.3.1 递归方法

重点是进行冲突检测：

1、摆当前棋子是在某行中选一个位置，行冲突是没有的。

2、列冲突：queenPos[j] == i；

3、斜线冲突：abs(queenPos[j] - i) == abs(k - j)。由于棋盘是方块，当前棋子与之前放置棋子的行差与列差相同说明在一条斜线上。

其中的变量：

i是当前行放置位置；

j是搜索queenPos数组已经放置的棋子（范围从第1个棋子到当前棋子k）；

k是当前放第几个棋子。

#include<iostream>
using namespace std;
const int M = 100;
int N;
int queenPos[M];//存放皇后的摆放位置
int sum = 0;//记一共有多少种解决方案void display()//《《不是必须的》》，用来图形化输出结果，@表示皇后
{int i, j;int k;cout << endl;sum++;for (i = 0; i < N; i++){cout << " ";for (k = 0; k < N; k++){cout << "---";}cout << endl;for (j = 0; j < N; j++){if (j == queenPos[i]){cout << "| ";cout << "@";}else{cout << "| ";cout << ".";}}cout << " |"<<endl;}cout << " ";for (i = 0; i < N; i++){cout << "---";}cout << "\n"<<endl;
}void NQueen(int k)
{//跳出条件，已经搜索到N皇后的第N行了。if (k == N)//N个皇后已经全部摆好{cout << N << "皇后的摆放位置是：";for (int i = 0; i < N; i++){cout << queenPos[i] + 1 << " ";}cout << endl;cout << "图解如下：" << endl;display();return;}//主要搜索过程for (int i = 0; i < N; i++)//在一行中逐个检测每个位置{int j;for (j = 0; j < k; j++)//和语句摆好的前几个皇后进行冲突检测{if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j)){break;//发生冲突，则检测下一个位置}}if (j == k)//搜到最后都没有break，说明该位置不与前面的皇后发生冲突，添加该位置{queenPos[k] = i;//将第k个皇后放在第i的位置上NQueen(k + 1);//搜下一个皇后的摆放位置}}
}
int main()
{cin >> N;NQueen(0);//摆放第0个皇后cout <<N<<" 皇后的解决方案有 "<< sum << " 种"<<endl;;return 0;
}

3.3.2 非递归方法

3.4 时间复杂度

该算法中每个皇后都要试探n列，共n个皇后，其解空间是一棵子集树，每个结点可能有n棵子树，对应的算法时间复杂度为 O(n^n)
利用显示约束排除两个皇后在同一行或同一列的方法，解空间树就是一棵排列树，因此共有n ! n!n!个叶子结点，所以算法的时间复杂度可以降为O ( n ! ) 

常见算法	时间复杂度	空间复杂度
哈希搜索	O(1) — 常数复杂度
二分搜索	O(log n) — 对数复杂度
回溯法--N皇后问题	O(n*2^n) — 线性复杂度
动态规划法--矩阵乘法	O(n*3)	O(n*2)
动态规划法--0-1背包问题	O(m*n)	/
动态规划法--跳台阶问题	O(n)	O(n)
动态规划法--最短路径问题	O(n*2)	O(n)
分治法	O(n*log n)	O(n)
贪心算法	O(m*n) O(n*2)	O(m*n) O(n*2)