dp with bit


  • 0
    P

    public class Solution {
    private int countOnes(int n){
    int rs = 0;
    while(n != 0){
    rs += (n & 1);
    n >>= 1;
    }
    return rs;
    }

    public int countArrangement(int N) {
        int M = (1<<N);
        int[][] dp = new int[N+1][M];
        
        for (int j = 0; j < M; j++){
            dp[1][j] = N - countOnes(j);
        }
        
        for (int i = 1; i <= N; i++){
            for (int j = 0; j < M; j++){
                for (int k = 1; k <= N; k++){
                    if (i % k == 0 || k % i == 0){
                        int pow = (1 << (k - 1));
                        if ((j & pow) == 0){
                            dp[i][j] += dp[i-1][j|pow];
                        }
                    }
                }
            }
        }
        return dp[N][0];
    }
    

    }

    // N = 2

    // dp[1][00] = N;
    // dp[1][01] = N - 1;
    // dp[1][10] = N - 1;
    // dp[1][11] = N - 2;
    // // dp[1][100] = N - 1;

    // dp[2][00] = dp[1][01] + dp[1][10] = 2
    // dp[2][01] = dp[1][11]
    // dp[2][10] = dp[1][11]
    // dp[2][2]


Log in to reply
 

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