C++ DP(Memoization) Bitmask solution


  • 0
    V

    In the bitmask i keep the record of the remaining elements to try in the recursion:

    int dp[17][1<<17];
    
    class Solution {
    public:
        
        int countrec(int ind, int N, int mask){
            if(dp[ind][mask]==-1){
                dp[ind][mask] = 0;
                if(mask==0){
                    dp[ind][mask] = 1;
                }else{
                    for(int i=1;i<=N;i++)
                        if(mask&(1<<(i-1))){
                            if(ind%i==0 || i%ind==0){
                                dp[ind][mask] += countrec(ind+1,N,mask-(1<<(i-1)));
                            }
                        }
                }
            }
            return dp[ind][mask];
        }
        int countArrangement(int N) {
            memset(dp,-1,sizeof(dp));
            return countrec(1,N,(1<<N)-1);
        }
    };

Log in to reply
 

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