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

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

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

研二开学记8月末去看了陈奕迅的演唱会，后来发现，不知道什么时候列的心愿清单，其实也都一个一个在实现，只是可能不是我原本计划的那样。有些事情真的就这样了，改变不了了，只能接受现实了。最近真的觉得，活着真没意思，活着真没意义，虽然很早之前就想明白了，活着的意义就是活着本身，但是自己心里其实还一直期待着，期待着自己是个特别的人。但是渐渐地渐渐地，我真真切切地感受到，自己真的是个普通人，没有什么上天的眷顾

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

剑指offer（专项突破版）15.4 并查集并查集是一种树形的数据结构，用来表示不相交集合的数据。并查集中的每个子集是一棵树，每个元素是某棵树中的一个节点。树中的每个节点有一个指向父节点的指针，树的根节点的指针指向它自己。并查集支持两种操作，即合并和查找。合并操作将两个子集合并成一个集合，只需要将一个子集对应的树的根节点的指针指向另一个子集对应的树的根节点。另一种操作是查找，即确定某个元素v处于哪

剑指offer（专项突破版）15.3 拓扑排序LCR113.课程排序分析将课程看成图中的节点，如果两门课程存在先修顺序那么它们在图中对应的节点之间存在一条从先修课程到后修课程的边，因此这是一个有向图。 对有向图进行拓扑排序的算法是每次找出一个入度为0的节点添加到序列中，然后删除该节点及所有以该节点为起点的边。重复这个过程，直到图为空或图中不存在入度为0的节点。 123456789101112131