0

我试图解决一个算法问题，该问题涉及计算给定数组中平方数组排列的数量。当且仅当每对相邻元素的总和是完全平方时，数组才是平方的。

我尝试使用位掩码 DP 来解决这个问题。其中表示以二进制格式表示的以状态dp[i][j]结尾的方形数组的数量（例如，1001111，其中 1 是已访问的节点，而 0 不是）。下面是两个版本的代码：ji

int n = nums.length;
int[][] dp = new int[1 << n][n];
Arrays.sort(nums);

for (int k = 0; k < n; k++) {
    if(k == 0 || (k > 0 && nums[k - 1] != nums[k])) {
        dp[1 << k][k] = 1;
    } 
}

// first version of dp traversal
for(int s = 0; s < (1 << n); s++) {
    for(int j = 0; j < n; j++) {
        if((s & (1 << j)) == 0) continue;
        for(int p = 0; p < n; p++) {
            int d = (int)Math.floor(Math.sqrt(nums[p] + nums[j]));
            if(!(d * d == nums[p] + nums[j])) continue;
            if((s & (1 << p)) != 0) continue;
            if(p > 0 && nums[p] == nums[p - 1] && (s & (1 << (p - 1))) == 0) continue;
            dp[s | (1 << p)][p] += dp[s][j];
        }
    }
}

// second version of dp traversal
for(int s = 0; s < (1 << n); s++) {
    for(int j = 0; j < n; j++) {
        if((s & (1 << j)) == 0) continue;
        for(int p = 0; p < n; p++) {
            int d = (int)Math.floor(Math.sqrt(nums[p] + nums[j]));
            if(!(d * d == nums[p] + nums[j])) continue;
            if((s & (1 << p)) != 0) continue;
            if((((s & ~(1 << j)) & (1 << p)) == 0)) continue;
            if(p > 0 && nums[p] == nums[p - 1] && (s & (1 << (p - 1))) == 0) continue;
            dp[s][j] += dp[(s & ~(1 << j))][p];
        }
    }
}

int ans = 0;
for(int l = 0; l < n; l++) {
    ans += dp[(1 << n) - 1][l];
}
return ans;

我感到困惑的是：当我尝试运行代码时，第一个版本给出了正确的结果，而第二个版本没有。我认为dp[s][j] += dp[(s & ~(1 << j))][p]意味着s结束状态j

s没有j那个状态的所有结果的总和是否以pifp和jare connected 结尾？

4

0 回答 0