used DP to solve this problem, only takes 31ms!


  • 0
    T

    Notice that in this question, the N<=15, so we can use hashmap to stored calculated information.

    public class Solution {
        public int countArrangement(int N) {
            if(N<=0) return 0;
            if(N==1) return 1;
            
            int[] used=new int[N+1];
            Map<Integer,Integer> map = new HashMap<>(); 
            return helper(map,used,N,1);
            
        }
        
        public int helper(Map<Integer,Integer> map,int[] used,int N,int index){
           if(index>N){
               return 1;
           }
            
           int key=hashKey(used);
           if(map.containsKey(key)){
               return map.get(key);
           }else{
               int sum=0;
               for(int i=1;i<used.length;i++){
                   if(used[i]==0 && (i%index==0||index%i==0)){
                       used[i]=1;
                       sum+=helper(map,used,N,index+1);
                       used[i]=0;
                   }
               }
               map.put(key,sum);
               return sum;
           }
           
        }
        
        public int hashKey(int[] used){
            int sum=0;
            for(int i=0;i<used.length;i++){
                sum=sum*2+used[i];
            }
            return sum;
        }
    }
    
    

  • 0
    T

    Slightly Modify my solution so that it can become simpler!

    public class Solution {
        public int countArrangement(int N) {
            if(N<=0) return 0;
            if(N==1) return 1;
            
            int[] used=new int[N+1];
            Map<Integer,Integer> map = new HashMap<>(); 
            return helper(map,used,N,0,1);
            
        }
        
        public int helper(Map<Integer,Integer> map,int[] used,int N,int cur,int index){
           if(index>N){
               return 1;
           }
            
           if(map.containsKey(cur)){
               return map.get(cur);
           }else{
               int sum=0;
               for(int i=1;i<used.length;i++){
                   if(used[i]==0 && (i%index==0||index%i==0)){
                       used[i]=1;
                       sum+=helper(map,used,N,(cur|(1<<i)),index+1);
                       used[i]=0;
                   }
               }
               map.put(cur,sum);
               return sum;
           }
           
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.