算法思想

这里按算法设计策略组织笔记：每一种策略先讲清核心思想与适用条件，再用经典问题完整走一遍「建模 → 递归关系 → 填表/搜索过程 → 代码实现 → 复杂度分析」。

把规模为 n 的问题分解为 k 个规模较小的相互独立的子问题，递归求解后再把子问题的解合并成原问题的解。

动态规划与分治法类似，都是把问题分解为规模更小的子问题。区别在于：分治法的子问题相互独立，而动态规划的子问题相互重叠——同一个子问题会在递归过程中被反复求解。动 …

贪心法在每一步决策时都选择当前状态下最优的选项，并且一旦做出选择就不再回溯。它期望通过一系列局部最优选择得到全局最优解——这个期望并不总是成立，因此贪心法必须配 …

回溯法是一种系统地搜索问题解空间的方法，本质是带剪枝的深度优先搜索。它从根结点出发，按深度优先策略搜索解空间树；搜索到某个结点时，先判断该结点是否可能包含问题的 …

分支限界法在问题的解空间树上搜索，但与回溯法的深度优先不同，它采用广度优先或最小耗费（最大效益）优先的策略扩展结点。每一个活结点只有一次机会成为扩展结点：一旦成 …

随机化算法在算法的执行过程中引入随机数，把随机数作为决策依据的一部分。这样做通常有两类收益：

在线性约束条件下，求一个线性目标函数的最大值或最小值：

显然有 P NP，但 P = NP 是否成立至今未解。目前普遍认为 P NP。