拓扑排序，以及区间dp相关试题
目录
1.有向无环图(DAG图）
2.AOV网:顶点活动图
3.拓扑排序
4.实现拓扑排序
力扣.207课程表
牛客.最长回文子序列
1.有向无环图(DAG图）
入度:表示有多少条边指向它
出度:有多少条边向外指出他
2.AOV网:顶点活动图
3.拓扑排序
找到做事情的先后顺序
一些活动必须要在某些活动之后，比如洗脚，我们在洗脚之前可以先烧水，接凉水，等等，所以他的顺序是不唯一的，哪个在前面都可以，当完成一个动作，可以删除一个动作
4.实现拓扑排序
1.找到一个入度为0的点，然后输出
2.删除与该点连接的边
重复1和2的操作，直到图中没有点或者没有入度为0的点为止。
没有入度为0的点，就是有环(所以这也是拓扑排序的重要作用，判断图中是否有环)
借助队列，来一次BFS即可
1.初始化:把所有入度为0点点，加入到队列中
2.
（1）当队列不为空时候，拿出队头元素，加入到最终结果中
（2）删除与该元素相连的边
（3）判断与删除边连接的点，是否入度变成0，如果入度变成0，加入到队列中
力扣.207课程表
能否拓扑排序:是看图中是否有环
有环是false;无环就是true;
如何建图呢？
建立图的概念:灵活使用容器
1.看稠密(看数据量)
邻接表:像是一个链表
List<List<Integer>edges; 链表嵌套链表
Map<Integer,List<Integer>>edges
可以改成String
2.根据算法流程,灵活建图
如何找到入度 int[]in=new int[n]
public boolean canFinish(int n, int[][] p) {//1.准备工作int[]in=new int[n]; //统计每一个顶点的入度//邻接表存图Map<Integer,List<Integer>>edges=new HashMap<>();for(int i=0;i<p.length;i++){int a=p[i][0],b=p[i][1];//b->a,先学b//看此时是否存在bif(!edges.containsKey(b)){edges.put(b,new ArrayList<>());}edges.get(b).add(a);//把a添加到b所连接的数组了in[a]++; //a的入度+1} //3.拓扑排序//(1)先把入度为0的点，加入到队列中Queue<Integer>q=new LinkedList<>();for(int i=0;i<n;i++){//判断哪一个点的入度为0if(in[i]==0)q.add(i);}//(2)bfswhile(!q.isEmpty()){int t=q.poll();//找到了，把里面的返回，假如找不到则返回一个空for(int a:edges.getOrDefault(t,new ArrayList<>())){in[a]--;//等同于删除边if(in[a]==0) q.add(a);}}//4.判断是否有环for(int x:in){if(x!=0)return false;}return true;}
public static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in=new Read();public static void main(String[] args) throws IOException{int n = in.nextInt();int m = in.nextInt();Map<Integer, List<Integer>>edges = new HashMap<>();int[][]p = new int[m][2];int k = 0;while (k < m) {p[k][0] = in.nextInt();p[k][1] = in.nextInt();k++;}//建图，统计每一个顶点的入度int[]in1 = new int[n + 1];for (int i = 0; i < m; i++) {int a = p[i][0];int b = p[i][1]; // a->bif (!edges.containsKey(a)) {edges.put(a, new ArrayList<>());}edges.get(a).add(b);in1[b]++;}//拓扑排序Queue<Integer>q = new LinkedList<>();for (int i = 1; i <=n; i++) {if (in1[i] == 0) {q.add(i);}}int[]ret=new int[n];//统计拓扑排序结果int pos=0;//统计第几个while (!q.isEmpty()) {//出度,检查入度为0的点int t = q.poll();ret[pos]=t;pos++; //a->b//它是获取开始入度为0的点，然后获取它连接的边，用l代替连接的那些点，然后进行l--,就是对应的边减少一块。他这个可以是a ,可以是别的，只是一个代号这种，他的含义是，获取入度为0的点，然后找到他的a,在a--，这样b的度就会减少for(int l:edges.getOrDefault(t,new ArrayList<>())){in1[l]--;if(in1[l]==0){q.add(l);}}} if(pos==n){//输出结果for(int i=0;i<n-1;i++){out.print(ret[i]+" ");}out.print(ret[n-1]);}else{System.out.print(-1);}out.close(); }
}
//自定义输入
class Read{StringTokenizer st=new StringTokenizer("");BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();
}
String nextLine() throws IOException{return bf.readLine();
}
int nextInt() throws IOException{return Integer.parseInt(next());
}牛客.最长回文子序列
选择的方法是区间dp,动态规划
初始化:
填表顺序:
需要从下往上，从左往右填表
返回dp[0][n-1]
public int longestPalindromeSubSeq (String ss) { //区间dp,动态规划char[]s=ss.toCharArray();int n=s.length;int[][]dp=new int[n][n];for(int i=n-1;i>=0;i--){dp[i][i]=1;for(int j=i+1;j<n;j++){if(i==j)dp[i][j]=1;else if(i<j){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);}}}}return dp[0][n-1];} }
