Optimization
Optimization
算法优化
- 贪心算法：
- 特点：在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
- 适用场景：问题满足贪心选择性质（局部最优解能决定全局最优解）和最优子结构。
- 例子：霍夫曼编码、最小生成树、Dijkstra。
- 动态规划：
- 特点：将复杂问题分解成简单子问题，以递归的方式解决子问题。不同于分治，动态规划会保存子问题的解，避免重复计算。
- 适用场景：问题具有最优子结构，且子问题重叠（不是互斥的）。
- 例子：斐波那契数列、背包问题等。
- 减治法：
- 特点：与分治法相似，但在每一步仅解决问题的一部分，减小问题规模，直到问题简单到可以直接求解。
- 适用场景：问题可以通过减少一部分来简化。
- 例子：插入排序、最大堆构建等。
联系与区别：
- 区别：
- 贪心算法在每步只考
结构优化
典型：前缀和/后缀和
空间换时间：
中途相遇法
双向搜索，或者叫折半搜索
典型应用
- 双向BFS，两头相对的bfs枚举+哈希表
- 两数之和，哈希表解法
- 数组的均值分割，二进制状压枚举+哈希表
可以令原时间复杂度开根号
折半搜索，又称为meet-in-the-middle。其做法为将整个搜索的过程分为两部分，然后每部分分别进行搜索，最后将得到两个答案序列，再将答案序列进行合并，即可得到最终的答案。
我们知道，搜索的时间复杂度往往是指数级别的。
比如，在每一层搜索时，假如都有两种选择，那么其时间复杂度为 𝑂(2𝑛) 。当 𝑛 较大时，往往会导致超时。此时，如果使用折半搜索，其时间复杂度将缩小为合并操作的时间复杂度𝑂(2𝑛/2+合并操作的时间复杂度) 。
直接使用「二进制枚举」，是指用二进制表示中的 0 和 1 分别代表在划分数组两边。
如果直接对原数组进行「二进制枚举」，由于每个 nums[i] 都有两种决策（归属于数组 A 或 B），共有 2^{30} 个状态需要计算。同时每个状态 state 而言，需要 O(n) 的时间复杂度来判定，但整个过程只需要有限个变量。
因此直接使用「二进制枚举」是一个无须额外空间 TLE 做法。
提示三：空间换时间
我们不可避免需要使用「枚举」的思路，也不可避免对每个 nums[i] 有两种决策。但我们可以考虑缩减每次搜索的长度，将搜索分多次进行。
具体的，我们可以先对 nums 的前半部分进行搜索，并将搜索记录以「二元组 (tot,cnt)的形式」进行缓存（map 套 set），其中 tot 为划分元素总和，cnt 为划分元素个数；随后再对 nums 的后半部分进行搜索，假设当前搜索到结果为 (tot′,cnt′)，假设我们能够通过“某种方式”算得另外一半的结果为何值，并能在缓存结果中查得该结果，则说明存在合法划分方案，返回 true。
通过「折半 + 缓存结果」的做法，将「累乘」的计算过程优化成「累加」计算过程。