DAG: Directed Acyclic Graph 有向无环图
在这道题中，重点有以下几点：
1.首先是建图，如何把矩形的嵌套关系保存到图中
2.图的遍历，求根节点到叶子的最长路径
3.在写dp的时候，要注意的是对每一个根节点的叶子节点，返回的是这些叶子及中的最长路径
4.每次遍历完一个叶子，要将高度high返回到初始状态
public class Destination{ //这是举行嵌套的问题 //这就是树的高度 private static int[][]Graph = new int[10][10]; private static int[][]Rect = { {1,2},{2,4},{5,8},{6,10},{7,9}, {3,1},{5,8},{12,10},{9,7},{2,2} }; public static void main(String[] args) { getGraph(); for (int i=0; i<10; i++){ for (int j=0; j<10; j++) System.out.print(Graph[i][j]+" "); System.out.println(); } System.out.println(traverseGraph()); } public static int traverseGraph(){ int max = 0; for (int i=0; i<10; i++){ //首先遍历10个节点 int high = 1; high = dfsGraph(i,high); if (high > max){ max = high; }; } return max; } public static int dfsGraph(int i,int high){ int temp = high; int max = 0; for (int j=0; j<10; j++){ if (Graph[i][j] == 1){ high = temp; //遍历完一个叶子节点，将高度恢复到初始状态 high++; high = dfsGraph(j,high); } //在这比较没每棵树的高度的得到以该 if (max < high){ //求所有的叶子节点中的最大值 max = high; } } return max; } public static void getGraph(){ for (int i=0; i<10; i++){ for (int j=i+1; j<10; j++){ if (Rect[i][0] < Rect[j][0]&&Rect[i][1] < Rect[j][1]){ Graph[i][j] = 1; }else if (Rect[i][0] > Rect[j][0]&&Rect[i][1] > Rect[j][1]){ Graph[j][i] = 1; } } } } }
