DFS，DP

class Solution {
    int count=0;
    boolean vis[];
    public int countArrangement(int n) {
        vis=new boolean[n+1];
        //我的问题1:不知道参数设置什么，有些遗忘，参数要去设置下标排到什么位置
     dfs(1,n);
     return count;
    }
    //实现
    public void dfs(int pos,int n){
   if(pos==n+1){
    count++;
    return ;
   }
   for(int i=1;i<=n;i++){
    if(vis[i]==false&&(i%pos==0||pos%i==0)){
        vis[i]=true;
        dfs(pos+1,n);
        vis[i]=false; //恢复现场
    }
    }
   }
}

class Solution {
    public int longestArithSeqLength(int[] nums) {
   //建标，为什么使用Map，因为假如要找那个距离i最近的下标，还需要一层遍历，这样很大概率超时，所以使用MAP来去存储距离最近的i那个下标
   //一遍dp,一边保存距离他最近的下标
   Map<Integer,Integer>hash=new HashMap<Integer,Integer>();
   //a的位置可能有nums[0]
   hash.put(nums[0],0);
   int n=nums.length;
   int [][]dp=new int[n][n];
   //我们只会用到dp的上半部分，因为i<j的
   for(int i=0;i<n;i++){    //初始化
    Arrays.fill(dp[i],2);
   }
   int ret=2;
   //i从0开始，j从1开始，那么dp表初始化的值本来就是2，没有意义，他不可能是3
  // ，所以需要i从1开始，j从2开始
 
  //固定了i位置，接下来枚举即可
   for(int i=1;i<n;i++){
    //j在i的后面，他本质还是一维数组
    for(int j=i+1;j<n;j++){
        //本质还是看一维数组  i :a j:b 以ij结尾
       // a-x=b-a,所以x=2a-b;
        int a=2*nums[i]-nums[j];
        //看a是否存在
        if(hash.containsKey(a)){
            //get(a)，获取a元素所在的下标
            dp[i][j]=dp[hash.get(a)][i]+1;
            ret=Math.max(ret,dp[i][j]);
        }
    }
    //说明i走完了，把i位置扔进哈希表里面
    hash.put(nums[i],i);
   }
return ret;
 
 
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
//dp[i]以i位置为结尾的子序列，最长子序列的长度
//状态表示分为两大类
//1.自己玩，长度为1
//2.跟在前面元素后面，构成递增子序列，nums[j]<nums[i]
   int max1=1; 
   int n=nums.length;
     int []dp=new int[n];
   Arrays.fill(dp,1);
   //从左往右
 
   for(int i=1;i<n;i++){
    for(int j=0;j<i;j++){
   if(nums[j]<nums[i]){
   //  j在 0 - i-1区间内动,为什么取一个最大值呢，因为j这个位置可以在i的前面也可以在后面，换句话说
                              //并不是一定在i-1这个位置，那么也就是说我们需要的是保存最大的dp[j]，而不是最近的,推荐是去调试一下。
    dp[i]=Math.max(dp[j]+1,dp[i]);
    max1=Math.max(max1,dp[i]);
   }
    }
   }
return max1;
    }
}