01. 状态压缩 DP 知识

[giscus[bot]]

01. 状态压缩 DP 知识

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

https://algo.itcharge.cn/10.Dynamic-Programming/07.State-DP/01.State-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] 吧？