矩阵嵌套 （Java代码）

解题思路:    

    代码里面都给的蛮详细，但是这里说一说我自己的坑。
    问题类型：DAG上的动态规划，求最长路的问题
    d(i)表示从结点i出发的最长路长度，他等于啥？我不知道，也不愿意去思考，问问下一个结点好了。

    d(j)表示他所连通的一个结点的最长路长度，i问j,你有好多长度呀，j回答过后
    i在他的基础上加1就行了

    状态转移方程就很简单了：ans=max{d(i),d(j)+1};

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	static int n=0;
	static int t[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		while(N-->0){
			n=in.nextInt();
			int arr[][]=new int[n+1][3];
			for(int i=1;i<=n;i++){//输入题目要求的数据
				for(int j=1;j<=2;j++)arr[i][j]=in.nextInt();
			}
			int max=-1;
			int G[][]=new int[n+1][n+1];
			t=new int[n+1];//用于记忆划搜索的数组
			
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if((arr[i][1]>arr[j][1]&&arr[i][2]>arr[j][2])||(arr[i][1]>arr[j][2]&&arr[i][2]>arr[j][1])) {//如果可以嵌套
						G[i][j]=1;//表示i和j是连通的，这一步很关键，存放连接图
					}
				}
			}
			for(int i=1;i<=n;i++)//从第一个矩阵开始遍历整个连通图
				if(dp(i,G)>max){//如果结点个数大于Max,更新
					max=dp(i, G);
				}
			System.out.println(max);
					
		}
	}

	private static int dp(int i, int[][] G) {
		// TODO Auto-generated method stub
		int ans=t[i];//
	    if(ans>0)//如果当前的节点位置已经被搜索过了，那么就直接返回，防止重复搜索
	        return ans;
		ans=1;
		for(int j=1;j<=n;j++){
			if(G[i][j]==1){//如果i和j是连通的，那么就继续找j连通的下一个点
				ans=Math.max(ans,dp(j,G)+1);//ans表示当前结点的最大路径
				t[i]=ans;
			}
		}
		return ans;
	}
}