05.03 背包问题滚动数组优化： $dp[w] = \begin{cases} dp[w] & w < weight[i - 1] \cr max \lbrace dp[w], dp[w - weight[i - 1]] + value[i - 1] \rbrace & w \ge weight[i - 1] \end{cases}$ 分割等和子集分析先把数组的和

单串线性 DP 问题 如果状态包含多个维度，但是每个维度上都是线性划分的阶段，也属于线性 DP。比如背包问题、区间 DP、数位 DP 等都属于线性 DP。 线性 DP 问题的划分方法有多种方式。 如果按照「状态的维度数」进行分类，我们可以将线性 DP 问题分为：一维线性 DP 问题、二维线性 DP 问题，以及多维线性 DP 问题。如果按照「问题的输入格式」进行分类，我们可以将线性 DP 问题分为：

05.01 动态规划基础 把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。 在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。 动态规划与

04.05 位运算 常用操作判断整数奇偶通过与1进行按位与运算，即可判断某个数是奇数还是偶数。 (x & 1) == 0 为偶数。 (x & 1) == 1 为奇数。 二进制数选取指定位如果我们想要从一个二进制数X中取出某几位，使取出位置上的二进位保留原值，其余位置为0，则可以使用另一个二进制数Y，使该二进制数上对应取出位置为 1，其余位

04.04 贪心算法贪心算法是一种改进的「分步解决算法」，其核心思想是：将求解过程分成「若干个步骤」，然后根据题意选择一种「度量标准」，每个步骤都应用「贪心原则」，选取当前状态下「最好 / 最优选择（局部最优解）」，并以此希望最后得出的结果也是「最好 / 最优结果（全局最优解）」。 换句话说，贪心算法不从整体最优上加以考虑，而是一步一步进行，每一步只以当前情况为基础，根据某个优

这是摘要，会在输入密码前显示

04.03 回溯算法一种能避免不必要搜索的穷举式的搜索算法。采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一步时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」。 明确所有选择：画出搜索过程的决策树，根据决策树来确定搜索路径。 明确终止条件：推敲出递归的终止条

04.02.05 分治算法把规模大的问题不断分解为子问题，使得问题规模减小到可以直接求解为止。分治算法从实现方式上来划分，可以分为两种：「递归算法」和「迭代算法」。 使用分治算法解决问题主要分为3个步骤： 分解：把要解决的问题分解为成若干个规模较小、相对独立、与原问题形式相同的子问题。 求解：递归求解各个子问题。 合并：按照原问题的要求，将子问题的解逐层合并构成原问题的解。 排序数组归并排序1

04.02 递归算法递推过程：指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题，直到达到结束条件时停止，此时返回最底层子问题的解。回归过程：指的是从最底层子问题的解开始，逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解。 具体步骤如下： 写出递推公式：找到将原问题分解为子问题的规律，并且根据规律写出递推公式。 明确终止条件：推敲出递归的终止条件，以及递归终止时的处理方法。

04.01 枚举算法204. 计数质数枚举（超时）考虑到如果i是x的因数，则$\frac{x}{i}$也必然是x的因数，则我们只需要检验这两个因数中的较小数即可。而较小数一定会落在$[2, \sqrt{x}]$上。因此我们在检验x是否为质数时，只需要枚举$[2, \sqrt{x}]$中的所有数即可。 123456789101112131415161718192021222324class Solu