友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

Transform and Conquer 变治法

D瓜哥最早知道变治法也是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。

变治法，就是基于变换的一种思想方法，首先把问题的实例变得容易求解，然后进行求解。

变治法的工作可以分成两个阶段：首先把问题变得更容易求解，然后对实例进行求解。根据我们对问题实例的变换方式，变治思想有3种主要的类型：

  1. 实例化简(Instance simplification) — 指将原问题变换为同样问题的一个更简单或者更方便的实例。一个典型的案例是：去重时，先排序，

    1. 列表预排序

      1. 检验数组中元素的唯一性

      2. 模式计算

      3. 查找问题

    2. 高斯消元法

      1. 系数矩阵的LU分解(LU decomposition)

      2. 计算矩阵的逆

      3. 计算矩阵的行列式

    3. AVL 树

  2. 改变表现(Representation Change) — 指将原问题变换为同样实例的不同表现。经典的栗子：霍纳法则。

    1. 多路平衡查找树（最简单的情况：2-3树）

    2. 求多项式的霍纳法则

    3. 两种二进制幂算法

    4. 堆排序

  3. 问题化简(Problem reduction) — 指把一个给定的问题变换为另一个可以用已知算法求解的问题。（归化思想）转换的难题在于如何找到一个变换的目标算法。典型案例是背包问题，背包问题的本质是线性规划。了解了线性规划的本质后，才能更好地解决高维的背包问题。

    1. 求最小公倍数

    2. 计算图中的路径数量

    3. 最优化问题（最大化问题(maximization problem)、最小化问题(minimization problem)）

    4. 线性规划（单纯形法、0/1背包问题）

    5. 简化为图问题

← Previous: Divide and Conquer 分治法 | ↑ Up: LeetCode 解题笔记 | Next: Backtracking 回溯 →