Java DP solution.


  • 1
    M

    We record elements we visited as a state. For example, "1001" means we visited 2 and 3 before. Because this question has small number of input, we can simply use integer as an key, otherwise, string will be better if the input exceed 32.

        int dp=0;
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        public int countArrangement(int N) {
            dp=(int)Math.pow(2,N)-1;
            return recurse(N,1);
        }
        public int recurse(int n,int level){
            if(level==n+1)return 1;
            if(map.containsKey(dp)) return map.get(dp);
            int mask=1,count=0;
            for(int i=1;i<=n;i++){
                if((i%level==0||level%i==0)&&(dp&mask)!=0){
                    dp^=mask;
                    count+=recurse(n,level+1);
                    dp|=mask;
                }
                mask<<=1;
            }
            map.put(dp,count);
            return count;
        }
    

Log in to reply
 

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