8.12 状态压缩动态规划

[giscus[bot]]

8.12 状态压缩动态规划

1. 状态压缩 DP 简介 状态压缩 DP：简称为「状压 DP」，是一种应用在「小规模数据」的数组 / 字符串上，结合「二进制」的性质来进行状态定义与状态转移的动态规划方法。 我们曾在「位运算知识」章节中，学习过「二进制枚举子集算法」。这里先来回顾一下如何通过二进制枚举子集。 1.1 二进制枚举子集 对于一个元素个数为 $n$ 的集合 $S$ 来说，每...

https://algo.itcharge.cn/08_dynamic_programming/08_12_state_compression_dp/

[sadcoldpig]

将集合 A 设置为全集：A = 1 << n ?

[itcharge]

已更正为 A = 1 << n - 1，感谢指正哈。

[Wangyzhou]

设为全集应该是 A = 1 << n - 1 吧？

[itcharge]

已更正为 A = 1 << n - 1，感谢指正。

[JayBigKing]

代码1的13行这里：
dp[state] = min(dp[state], dp[state ^ (1 << i)] + (nums1[i] ^ nums2[one_cnt - 1]))
我感觉是 nums2[i] ^ nums1[one_cnt - 1] 吧？

[zhy5662]

枚举集合 A的子集（包含 A）内容中的subB啥意思？另外此代码的含义是不是枚举“非空”子集？

[zhy5662]

设A为全集不应该是 A = (1 << n) - 1吗？减法的优先级高于左移，应该需要加括号吧？

[zhy5662]

枚举全集的所有子集第三行代码：
if (state >> i) & i: # 如果第 i 位元素对应二进制位 1，则表示集合中选取了该元素
条件应该写成(state >> i) & 1 或者 state & (1 << i)吧？