北邮考研复试机试准备过程（已上岸）

纯自用请勿转载，用来给自己最后复习和捋思路用的，主要参考牛客网+王道机试指南，C、C++混用。考研人太久不写代码了…什么都不记得了，从头开始过一遍吧。
黑色代码段是要记住的重点函数/方法。每天下午做几个小时，一共不到一周完成。
C++

#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;
cin>>m//输入
cout<<n//输出
//听说cin、cout效率低会超时，后面没用

//常用库
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
scanf("%d",&m);//输入
printf("%d",m);//输出

一、牛客网北邮真题

先拿往年真题找找手感

1.KY187 二进制数

任务：int类型数转二进制数
思路：函数内部递归、按位与n&1、>>右移
r=n&1; //r取n的二进制的最末位，[按位与]还可以用于判断奇偶性
n>>1;//n右移一位，例如1011变成101再变成10

2.KY198 找最小数

任务：输入n对数，找最小对
思路：很简单，每行边输入边比较，最后得到最小对
注意：cin>>x>>y中间有“ ”空格会报错，不知道为什么，但是输出的时候可以cout<<x0<<" "<<y0;

3.KY199 查找

//太简单了。。注意事项就是当数据量较大时，如果想要降低复杂度，则可以先对数组进行排序。对于小数据量直接用嵌套循环就能完成。

4.KY188 哈夫曼树

任务：哈夫曼树，输入数量n，以及n个权值，求得所有结点的值与权值的乘积之和的最小值
思路：所求值=所有非叶节点之和。所以先排序，按照构建哈夫曼树的方法，边自底向上构造，边计算sum值。每轮将两个结点结合之后再将整个数组重新排序，再次循环计算，直到将n-1个非叶节点（叶结点一共n个）全部累加完毕为止
排序可以用以下库函数qsort

int cmp(const void* a,const void* b){return *(int*)b-*(int*)a;
}

qsort(num,n,sizeof(num[0]),cmp);

5.KY190 查找第k小数

任务：每组输入n，然后输入n个整数(1<=n<=1000)，再输入k，查找第k小的数（相同视为一样大）
思路：
第一种：输入过程做是否存在相同数的判断，相同大小不重复储存，使存数据的数组内都是不一样大小的数据。然后对数组内数据排序。最后找出第k个即可（没试过，用快排会很快！看到大佬有1ms的）

第二种：（我自己用的，傻瓜算法）直接设一个大小1000的数组，初始化全为0.接着输入循环，输入的整数为i，则将a[i]设置为1。最后找到数组中第k个为1的所在的位置m（用k–，判断到k=0跳出），输出m即可。感觉就是舍弃空间换时间的算法。

6.KY194 树查找

任务：每组输入一个n(1<=n<=1000)，然后将树中的这n个节点依次输入，再输入一个d代表深度。输出该树中第d层得所有节点。
思路：对于完全二叉树而言，总结点数是2^depth-1，
对应第d层的节点个数为2^(d-1),就可以用一种很暴力的算法，先推总depth，再输出从d-1层到第d层的数。

#include <math.h>//求幂次的时候用到math库里面的pow函数，double类型可强制转换

pow(x,y);//求x的y次幂

7.KY223 二叉排序树

任务：建立二叉排序树，然后分别前序中序后序遍历
思路：难题。要写的代码很多。步骤1：如何建立二叉排序树？步骤2：三种遍历的实现
参考了王道的写法。。待补充，主体如下：
1结构体，create函数，insert函数，前中后序遍历函数
用到指针、初始化结点

8.KY191矩阵幂

任务：求n*n矩阵的k次幂
思路：简单题。就三个矩阵，一个是初始矩阵，一个是中间用来计算的矩阵，一个是最终矩阵。在求幂次的过程中不能把矩阵弄混了，否则会计算结果出错。
要不就用结构体，再用函数调用；
要不就直接写，因为结构体实现有一点麻烦。
注意：容易忽略k=1的情况导致边缘用例不通过！

二、王道机试指南（2013）

跟着王道系统学习

第二章经典入门

2-1排序*（重要！）

例2.1

法1：手写冒泡排序：
（1）当已经不再发生交换的时候就说明排序完成，用一个flag来监视。
（2）注意溢出，在内部循环中，比如可能j<n-1
法2：快排：可以直接用c++库函数！！

include <algorithm>
using namespace std;

比如你希望buf升序输出，用快排库函数

sort(buf,buf+n);//起始地址，结束地址

若希望降序输出，则

bool cmp(int x,int y){
return x>y;
}

sort(buf,buf+n,cmp);//第二种重载方式，+比较函数

例2.2

任务：按照学生的成绩从低到高排序，相同则按照姓名和年纪
思路：还是用sort，只是sort的对象的类型从int数组变成了Student数组，只需要在cmp中去具体定义每两个传进去的Student对象怎么比较就可以了
注意：

include <string.h> //1.为了用char数组要引入

比较两个名字（字符串）的名字字典序的方法，很重要！

int tmp = strcmp(x.name, y.name);
//两个字符串自左向右逐个字符相比（按ASCII值大小相比较）
if (tmp != 0) return tmp < 0;//结果：s1<=>s2对应tmp-0+

2-2 日期类

2.3日期差值

重点1：这类日期区间问题——把原区间问题统一到起点确定的区间问题上，相当于所有日期都与一个特定的原点日期去比较，再计算差值即可
重点2：闰年2月只有29天。闰年定义：【年数】无法被100整除，但是可以被4整除或能被400整除

#define ISYEAP(x) x%100!=0&&x%4==0||x%400==0?1:0
//定义宏判断是否是闰年

思路：（1）提前用二维数组存好一年中各月份的天数（普通年份，闰年）（2）创建日期类，定义计算函数（3）将进来的日期都与原点进行比较

例2.4求几天周几（复杂）

同上，取标准日期作比较，略复杂

2-3 Hash

例2.5 求某一分数的学生人数

很简单的题。。。
方法一：逐个与key比较，count++
方法二：由于分数有范围0~100，所以可以直接设置一个分数数组，在对应位置每次有一个学生就+1，最后输出对应key位置的值就是人数

例2.6 大n排序

当就算用nlog级别的算法排序时复杂度已经超过了千万级，说明不能再用排序算法了！！
解法：所以同上，用hash来统计每个数字是否出现1/0，然后找前m大仅需从后向前遍历，最多仅是百万级别复杂度

#define OFFSET 500000 //宏定义一个常量用来补偿数组下标偏移

2-4 排版题

例2.7 输出梯形

简单题，搞清楚规律就行

例2.8叠筐

对于这种跟输出习惯不一样的题，先将我们要输出的数据，按照希望输出的顺序存放在一个已经提前初始化好的二位数组（代替矩阵）中——计算对应的坐标所需要放置的字符是哪一个。
最后直接用二维数组按序输出实现即可

2-5 查找

例2.9 找x

方法一：遍历查找。直接用key跟数组中一一对比即可，没技术含量
方法二：二分查找。时间复杂度更低（在牛客网？还是leetcode做过，可以去看一下）

例2.10 查找学生信息

难点1：又是时间复杂度题！！
每次遍历查询数组则是O(n*m)的时间复杂度，达到了千万数量级，所以不能用了
难点2：序号是01,02…所以用字符串输入，在后面比较也要用字符串比较函数
解法：用二分查找，从中间开始比较key，每轮查找条件是【base<=top】

int tmp = strcmp(buf[mid], x);
//两个字符串自左向右逐个字符相比（按ASCII值大小相比较）
//结果：中间序号<=>要求序号 对应 tmp= -0+

2-6 贪心算法

每次总选择当前最优，但不会从整体把握。有时能得到最优解。

例2.11 FatMouse’ Trade

要求用给定的钱买到重量最重的物品总数
思路：（1）设置物品结构体goods，变量：重量、价值、性价比。（2）计算每个物体性价比，对性价比降序排序（3）购买各个物品，跳出条件为【物品有剩余&&钱>0】,先尝试是否能全部买下该物品，不能时就把money花完然后结束

例2.12 今年暑假不AC（思路很重要）

任务：根据电视节目的开始和结束时间，选出能看到最多完整电视节目数量的一个看电视策略
思路：贪心策略：每轮看完当前节目之后，选择【还未开始&&结束时间最早】的节目
（1）创建program结构体（2）按照结束时间升序排列所有节目[用sort+cmp]（3）记录初始当前时间时间=0，每次看完节目将【当前时间=该节目结束时间】
贪心的思路：开始最早？持续最短？结束最早？可以找一些反例。。。

第三章数据结构

3-1 栈的应用

引入模板库中的栈，使用方法如下

#include<stack>

stack<int> S;//保存数据类型为int的栈S

S.push(i); //压栈
int x=S.top();//取顶部元素
S.pop();//弹出栈顶元素

例3.1括号匹配

从左到右遍历字符串，用压栈+栈顶元素来判断是否有不可匹配的括号

for(int i=0;str[i]!=0;i++) // 判断字符串结束：ascii=0；遍历字符串的语法

if (s[i]=='(') {}//注意！是单引号哦，否则会报错

思路：（1）用了两个字符串来分别存储输入输出信息，在遇到不匹配括号的同时存入错误信息，这样一次遍历就能完成任务（2）栈是int类型，存数组下标，最后对没匹配完的左括号统一修改输出内容
！注意：当一个栈的栈顶没有信息时，调用取栈顶s.top()会报错，可以预存一个空格/先判断是否为空

if （s.empty()==false）//堆栈非空

例3.2 简单计算器（复杂）

经典利用堆栈对表达式求值题
思路：（1）两个(int和double)堆栈，分别存运算符和数字（2）需要一个比较函数，参数为两个运算符，返回两个运算符的优先级大小比较结果（3）运算符栈顶部人为存一个标记运算符，用来判断表达式运算是否结束
可以写

if(str[]>='0' && str[i]<='9')//表示当前字符为数字

将字符串转换为数字

for(;str[i]!=' ' && str[i]!=0;i++){retn*=10;retn+= str[i]-'0';//这里计算的是二者ASCII码的差值！！
}

判断输入只有一个0的语句

if (str[0]=='0' && str[1]==0) break;

每轮循环开始前还要清空栈——判断栈是否空

3-2 哈夫曼树*

目标：计算最小带权路径长度和：所有中间结点/非叶子节点的权值和
方法：用堆->优先队列（标准模板库）

#include<queue>

priority_queue<int> Q;//默认为大顶堆
priority_queue<int,vector<int>,greater<int>> 	Q;//小顶堆

用栈、队列等必须做：（1）操作前判断空+清空（2）判断堆中元素数量>1

while(Q.size()>1)

思路：每次累加完两个最小元素的和之后，要把该中间节点的值作为新的元素压回优先队列中，直到堆只剩一个根元素

3-3 二叉树*

必须要记住的怎么写：
1.结构体
2.初始化节点

BiNode Tree[N];
BiNode *Create_BST(){Tree[loc].lchild=Tree[loc].rchild=NULL;//初始化一个节点return &Tree[loc++];
}

二叉排序树的建树方法

BiNode *Insert(BiNode *T,int x){//传进来树的地址，返回一个地址if(T==NULL){T=Create_BST();//建立节点T->data=x;return T;}else if(x<T->data){T->lchild=Insert(T->lchild, x);}else if(x>T->data){T->rchild=Insert(T->rchild, x);}return T;
}
//在排序二叉树中插入节点的算法

3.遍历（递归）

void preOrder(BiNode *T){printf("%d ",T->data);if(T->lchild!=NULL){preOrder(T->lchild);}if(T->rchild!=NULL){preOrder(T->rchild);}
}//前序遍历

3.4二叉树遍历（没做）

任务：通过给出的前序、中序遍历，还原二叉树，输出后序遍历
方法：（1）用字符串保存前序、中序遍历结果。（2）用前序遍历的第一个字符作为根节点，申请空间，并找该根节点字符在中序遍历中的位置（3）对左右子树递归，先左后右

Node *build(int s1, int e1,int s2,int e2) { //由字符串的前序遍历和中序遍历还原树，并返回其根节点,其中前序遍历结果为由str1[s1]到str2[e1]，中序遍历结果为str2[s2]到str2[e2]

3-4 二叉排序树*

3.5 二叉排序树

与牛客网重复

3.6 二叉搜索树

任务：判断两棵二叉树是否相同
方法：对每两棵树进行包括中序遍历在内的两种遍历，当结果相同时，就可以判断两棵树相同

第四章数学问题

4-1 %运算符（没什么可看的）

4-2 数位拆解

例4.2 特殊乘法

两个数字都是亿级别以上的数字，求各位相乘之和。题不难，两种解法，感觉我选的那个更简单
方法一：对x做数位拆解，利用/和%，循环，分别将各位的数字拆分出来，再计算结果
方法二（我自己开始用的）：将两个数字作为字符串读入，然后对他们每个字符遍历计算与’0’的ASCII码差值得到各位并求解

4-3 进制转换*

学习m到十进制和十进制到n进制的转换
10->2：对x%2再x/2…直到x%2的结果为0为止，每次x%2得到的都是从最低位开始的各位数字
m->10：就参考二进制就行

例4.2 又一版A+B

求十进制的m进制数，用ans数组来存放各位数字，可以用一个【size++】来对个数计数

for (int i = 0;( (k %m)!= 0)||((k/m)!=0); i++) {ans[i] = k % m;//求模k = k/m;//除以m}

！注意：因为a，b两个数字是最大在int范围内，而两个数字之和可能会超过int所能表示的最大值，导致溢出。所以选用long long数据类型，输出转义字符为%lld

例4.3 数制转换

思路：a进制转10进制，10进制转b进制
难点：如何区别和计算输入进来的数字/大写字母/小写字母？？

int lenth=strlen(str)//可以求字符串长度，跟数组的n一样的

if(str[i]>='0'&&str[i]<='9'){x=str[i]-'0';//计算0~9之间的数字
}else if(str[i]>='a'&&str[i]<='z'){x=str[i]-'a'+10;//计算小写字母
}else{x=str[i]-'A'+10//计算大写字母
}

4-4 最大公约数GCD

求同时满足a%c=0,b%c=0的最大整数c
方法：用欧几里得算法：
当a、b全为0——最大公约数不存在
当a或b=0——最大公约数为非零的那个
a、b都不为0——令a=b,b=a%b，重复该过程（可以递归，return(b,a%b)即可)）

4-5 最小公倍数LCM

求同时满足c%a=0,c%b=0的最大整数c
方法：最小公倍数=（a*b）除以他们的最大公约数

4-6 素数筛法

例4.6素数判定

测试一个数是不是素数：O(sqrt(n))
方法：对每个输入的值依次测试（1，其平方根] 的数字能否整除他即可。
利用sqrt开根函数

int bound = (int)sqrt(x)+1;//计算枚举上界，为防止double值带来的精度损失，所以采用根号值取整后再加1（多枚举一个）

依次枚举从2-bound的数能否整除x

if (x%i==0) return false;//只要有一个能则必不为素数

例4.7素数

找某范围内的所有素数
方法：每找到一个素数，即将它的所有倍数均标记为非素数。当遍历到一个数未被标记过，则确定他为素数，并继续标记它的所有倍数。

for(int j=i*i;j<=10000;j+=i){
mark[j]=true;
}//标记倍数的方法，注意j初始值和循环操作，减少时间复杂度，优化程序

最后未被标记过的所有数为素数

4-7 分解素因数

例4.8质因数的个数

求某个正整数n的所有质因数的个数（包括重复的）=求所有素因数的幂指数之和
方法：（1）提前找到在n的最大范围内的所有素数，存下来（2）对每个n，遍历所有素数，找出n的因数（3）通过/除确定每个因数的幂指数（4）累加幂指数

例4.9整除问题（很难…）

给定n，a，范围[2,1000]，求最大的k，使n! 可以被a^k 整除``但不能被a^(k+1)整除
难点：n!和a^k可能数值很大，甚至连longlong都无法保存，因此不能直接用求余数来算
方法：分别对n!和a分解素因数，看n!的素因数中各数的幂指数，再对比a中相同素因数的幂指数，对应相除就可得到每个素因数的商，商最小值就是k

4-8 二分求幂（没看懂啊，有空再看吧，先用pow）

例4.10人见人爱A^B

求A^B∈[1,10000]的最后三位表示的整数
思路：不能直接算再求后三位，因为实在太大了。分解a^b变为``【若干个 a的2^k次的积】,

4-9 高精度整数（不太重要）

不能用任何数据类型的高精度整数，只能自己创建结构体来解答题目，把输入当做字符串进行保存。。。

第五章图论

5-1基础知识

两种方法表示图：
（1）邻接矩阵：用二维数组来保存，edga[i][j]，1表示存在边，0表示无边。还能用来保存权值（带权图），此时若不存在边则用特殊字符如-1来表示。
适合稠密图、频繁地判断某特定节点对是否相邻
（2）邻接链表：适合存在大量遍历邻接节点的操作，而较少判断两个特定结点之间的关系时
推荐用STL库中的标准模板std::vector

#include<vector>
struct Edge{int nextNode;//邻接下一个结点的编号int cost;//该边权重
};

创建一个数组，保存的是vector对象，edge[i]表示为结点i建立的单链表

vector<Edge> edge[N];

相关操作（背*）:clear,pushback,size,erase

for(int i=0;i<N;i++){edge[i].clear(); //清空所有结点的单链表
}//初始化

Edge tmp;
tmp.nextNode=3;tmp.cost=38;
edge[1].pushback(tmp);
//把边tmp加入到结点1的单链表中

for(int i=0;i<edge[2].size();i++){int nextNode=edge[2][i].nextNode;//2号结点的第i条边所对应的邻接结点int cost=edge[2][i].cost;//读出权值
}

edge[1].erase(edge[1].begin()+i, edge[1].begin()+j+1);
//i是第一个要删除的元素编号，j是最后一个要删除元素的编号

5-2并查集

·路径压缩：查找某点的根节点时使在某点和根节点之间的所有结点都指向根节点。优化了后续查找工作。

int findRoot(int x){if(Tree[x]==-1) returnx;else{int tmp=findRoot(Tree[x]);Tree[x]=tmp;//将当前节点x的双亲结点设置成最后返回的根节点编号tmpreturn tmp;}
}

例5.1 畅通工程

任务：给出几条路径，令所有路径上的结点对之间都直接或间接相连
思路：每个结点开始都是孤立的连通变量，每次读入一条建成的边，就将边的两条顶点所在的集合合并，最后看有多少个集合就可以知道有多少个连通分量。road=set-1（根节点个数-1）

a=findRoot(a);
b=findRoot(b);
if(a!=b){Tree[a]=b;}
//两个顶点不在一个集合，则合并这两个集合

！注意：对于提前定义的全局变量/数组，一定要记得如果是多组输入的话，在每一轮的时候开头要将会用来判断的变量都初始化/复原成最开始的样子！！！！

例5.2 More is better

任务：同上，但最后要输出最大的集合的节点个数
方法：还是用findRoot，新增一个各集合的计数变量，在合并两点所在集合的同时在本集合的计数变量上加上对方的集合内的个数。最后判断哪个集合最大则输出哪个的节点数量

5-3最小生成树MST*（Kruskal算法）

·生成树：包含所有结点的、不存在回路的连通子图
·最小生成树：所有生成树中边权值和最小的
·常见问题（例）：在基站间修光缆来使所有基站间可以通信，最少需要多长的光缆

例5.3还是畅通工程

任务：令所有城市连通且道路总长度最小
思路：（1）建立边结构体，包括：两点的编号、该边的权值（2）录入所有边，对它们从小到大排序（3）并查集，对权值从小到大的每一条边上的一对结点用findRoot，如果两节点不在同一集合，则合并两个集合，并累加该边的权值（4）输出结果

例5.4 Freckles

任务：求各点之间能连接的总长度最小
思路：一样求最小生成树，唯一的差别是边的权值不是直接给的，所以要先构建计算各点间距离，然后同上解题即可
提示：开根号sqrt(x)，用double

5-4 最短路径*

找两个特定结点间的最短路径。
1.Floyd算法：
求每对顶点之间的最短路径（全源最短路）
步骤：（1）用邻接矩阵edge[i][j]（二维数组），初始存i到j直达的距离。（2）考虑可以经过的结点增加了编号为1的结点，则比较edge[i][1]+edge[1][j]和edge[i][j]的大小，若前者小则更新edge[i][j]。循环增加结点至N
2.Dijstra算法
求从一特定起点出发到其他所有点的最短路径（单源最短路）
步骤：（1）从一个结点1出发，比较所有1的相邻结点的路径长度，选出距离最短的结点加入集合K（2）遍历所有与集合K中的元素U相邻的非集合K结点V，按照U的最短路径d，找到到下一个距离U最近的V，并把V加入K，设置它的最短距离为d+d(uv).（3）若集合K中已经包含了所有的点，算法结束，否则重复2
用vector模拟邻接链表

例5.5最短路

任务：求从点1到点N的最短路径
·方法1：用Floyd算法
步骤：（1）对邻接矩阵初始化，-1表示无穷，自己到自己为0（2）将所有路的信息赋值，要注意是无向图赋值。

ans[a][b]=ans[b][a]=c

（3）从1到N不断添加允许经过的中间结点编号，遍历所有ans[i][j]

if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j]){ans[i][j]=ans[i][k]+ans[k][j];//经过k可以获得更短的路径

（4）循环结束后输出ans[1][n]

方法2：用Dijstra算法
步骤：
（1）创建链表元素结构体、邻接链表(vector)

struct E{
int next;//相邻结点
int c;//边的权值
};
vector<E> edge[101];//邻接链表

（2）初始化邻接链表

for(int i=1;i<=n;i++) edge[i].clear

录入各边，双向都要录入

scanf("%d%d%d",&a,&b,&c);
E tmp;
tmp.c=c;
tmp.next=b;
edge[a].push_back(tmp);//从a到b方向的边加入邻接链表
tmp.next=a;
edge[b].push_back(tmp);//从b到a方向的边加入邻接链表

（3）一个数组mark标记各结点是否在集合K中，一个数组dis标记到每个节点的最短路径长度。初始化距离为-1，属于为false。
（4）从起始节点1开始，距离为0，属于k为ture。不断遍历与【新加入集合结点】直接相邻的边

for(int j=0;j<edge[newP].size();j++){//遍历newP的边int t=edge[newP][j].next;int c=edge[newP][j].c;if(Dis[t]==-1||Dis[t]>Dis[newP]+c)//若该点不可达，或可以更新该点最短到达距离Dis[t]=Dis[newP]+c;
}

（5）遍历所有节点，找到【还不在K内&&可达&&由1至它距离最小】的那个点，使它成为最新的newP，并加入K
（6）最后从dis数组中输出需要的最短路径

例5.6最短路径问题（没写，没时间了）

5-5 拓扑排序*

第六章搜索

6-1枚举

6-2广度优先搜索BFS*

例6.2胜利大逃亡（较难，建议看看没时间不用复现）

任务：在三维坐标中，找到一条从原点到(A-1,B-1,C-1)的最短合法路径。
思路：从原点出发，对解答树进行遍历，每次状态转移时拓展出尽可能多的新状态。
剪枝——限制拓展，对于重复出现的点，不需再次重复拓展，则所需遍历的状态总数变为ABC
方法：结构体+队列实现，存储状态对象

struct N{
int x,y,z;
int t;
}
queue<N> Q;//存放状态

在Q中还有元素的情况下，得到队头状态

N now=Q.front();

接着判断该状态的相邻6结点，【在立方体内&&不是墙&&未得到过】的变成新的状态，耗时=now.t+1，标记并push入队列
最后当搜索结束（走到终点），返回耗时

6-3递归

6-4递归应用

6-5深度优先搜索DFS*

第七章动态规划

7-1递归求解

一共有多少种方式呢？

例7.1 N阶楼上楼问题

代码不难，思路很重要——递推
思路：n>2时，只考虑每次上台阶的最后一步怎么走——即从n-1阶经走一步走到n阶，或者从n-2阶经走两步到n阶。这样最后一步都是确定的，所以可知到达n阶的总上楼方式为F[n]=F[n-1]+F[n-2]

例7.2 不容易系列之一

比较难这道题，求给n个人装信，全部都装错信封的概率。此处用的是错排公式：F[n]=(n-1)*F[n-1]+(n-1)*F[n-2].核心思想也是递推，分成两类状态，均与上一级相关，但是不好描述，建议看书上解释。

7-2最长递增子序列LIS

若在子序列中，当下标X>y,ax>ay，我们称这个子序列为原序列的一个递增子序列（子序列不是子串，不需要必须连续）
最长递增子序列的递推公式

例7.3 拦截导弹

任务：求最长不增子序列
思路：将以每个导弹结尾的最长不增子序列长度都计算出来（即F[i]全部算出来），存在一数组内。最后找出最大的F[i]输出
计算：两层循环。第一层是遍历顺序到达的每个导弹i，第二层遍历是导弹i之前的所有不比它小的导弹的F[j]，找到一个最大值，+1存入F[i]

7-3最长公共子序列LCS*

在这里插入图片描述
可以看出，最长公共子串也是依靠递推的方法

例7.4 Coincidence

感觉王道的题目有点问题（不知道是不是我的问题），参考别的地方看来的解法：
（1）把两个字符串分别以行和列组成一个二维矩阵（2）两层循环，比较每个行列字符是否相等，相等为1，否则为0
（3）可以边判断，边存储每一个位置的最长公共子串长度，即

dp[i][j]=1+record[i-1][j-1]

（4）查找出值为1的最长对角线，即为最长公共子串

7-4状态与状态转移方程

7-5动态规划问题

7-6背包

01背包：通过求解子问题推导大问题
在这里插入图片描述

三、Practice

PTA平台、牛客网上的练习，练手

1.PAT (Basic Level) Practice

1025.反转链表

写了半天，挺难的，要分情况讨论，核心思想就是反转链表。
要注意的是：
（1）如果数据中有类似00100,00020的数，后面需要输出，要注意把它存为字符数组，否则int类型会自动去掉前面的0
（2）字符串的比较、赋值函数

strcmp(x,y);//按位比较ASCII码。x<y,返回-1；
strcpy(x,y);//字符串赋值

（3）指针p，如果是结构体类型，要用p->data,不能用p.data

2.牛客网

（1）求二叉树深度

int maxDepth(TreeNode* root) {if(!root) return 0;int lDepth = maxDepth(root->left);int rDepth = maxDepth(root->right);return 1+(lDepth>rDepth?lDepth:rDepth);//很常用，要记住哦}