LeetCode 526. A graceful arrangement***

Specific ideas ：

DP Memory search ;

The difficulty lies in two places ：

1. DP Ideas ;
2. How to use bits to calculate ;

Utilization bit bit To express those positions , Don't care who it is ;

enumeration 1～n position , In this case, it means to consider the i How much profit can a bit make ,dp[i][state];

among state Represents the status value ;

Enumerate all States , But notice , Because now enumerate to i position , Fill in the total i Number , therefore state Whether it is necessary to determine how many have been used , Whether it is i individual , That is, the statistics of each state bit 1 The number of ;

Check the legal status 1～n Enumeration , First of all, the numbers you fill in should meet the requirements of the topic , Secondly, for this number , It must be in state Indicates that... Has been used ;

Add it up ;

Specific code ：

1. to flash back ：

class Solution {
    
public:
    int countArrangement(int n) {
    
        vector<bool>vis(n,false);
        int ret=0;
        dfs(vis,n,1,ret);
        return ret;
    }
    
    void dfs(vector<bool>& vis,int& n,int cnt,int& ret){
    
        if(cnt==n+1){
    
            ret++;
            return;
        }
        for(int i=1;i<=n;i++){
    
            if(vis[i])
                continue;
            if(i%cnt!=0&&cnt%i!=0)
                continue;
            vis[i]=true;
            dfs(vis,n,cnt+1,ret);
            vis[i]=false;
        }
    }
};

2. state DP：

class Solution {
    
public:
    int countArrangement(int n) {
    
        int mask=1<<n;
        vector<vector<int>>dp(n+1,vector<int>(mask,0));
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
    
            // Before enumeration i A place ;
            for(int j=0;j<mask;j++){
    
                int num = __builtin_popcount(j);
                if(num!=i)
                    continue;
                for(int k=1;k<=n;k++){
    
                    if((1<<(k-1)&j)!=0&&(k%i==0||i%k==0)){
    
                        dp[i][j]+=dp[i-1][(~(1<<(k-1)))&j];
                    }
                }
            }
        }
        return dp[n][mask-1];
    }
};