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

• 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;
}
}

``````

• 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;
}

}
}
``````

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