4.贪心法
4.1 算法思路
并不从全局最优上考虑，而是每次都做当前的局部最优选择。
虽然贪心不是对所有问题都能够得到全局最优解，但事实上很多问题都能够得到。
4.2 适用范围
使用贪心算法需要满足以下性质：
① 贪心选择性质
该性质是说所求问题的整体最优解可以通过一系列局部最优的选择来达到。而要确定一个问题是否具有这种性质，必须证明每一步所做的贪心选择最终会导致全局最优解。
②最优子结构性质
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。这种性质是问题可用动态规划或贪心解决的重要特征。
4.3 算法求解过程
①建立数学模型描述问题
②把求解的问题分成若干个子问题
③把每个子问题求解，得到子问题的局部最优解
④把子问题的局部最优解合成原来解问题的一个解
4.4 算法证明
其实很多时候我们能凭借生活经验和直觉判断出这就是个贪心问题，但是解题是最难的便是证明它。
我们可以去证明问题的贪心选择性质和最优子结构性质来证明贪心算法的正确性。
最优子结构的证明思路：
a) 定义子问题空间，做出一个选择从而产生一个或多个子问题。子问题空间的定义结合需要求解的目标和选择后子问题的描述刻画来考虑。
b) 利用“剪切-粘贴”证明作为最优解的组成部分的每个子问题的解也是它本身的最优解。如果子问题的解不是最优解，将其替换为对应的最优解从而一定能得到原问题一个更优的解，这与最初的解是原问题的最优解的前提假设矛盾，因此最优子结构得证。
贪心选择性质的证明思路：
贪心的本质是局部最优解能产生全局最优解，即产生两个子问题S1和S2时，可以直接解决子问题S1（在子问题S1中，使用贪心策略选择a作为局部最优解)然后对子问题S2进行分解，最终可以合并为全局最优解。
因此，要证明贪心选择性质只需要证明存在一个最优解是通过当前贪心选择策略得到的，反过来，即证明通过非贪心策略得到的原问题的最优解中也一定包含局部最优解a。
Exchange Argument方法
定义通过非贪心策略的选择可以得到的一个最优解A，将最优解中的元素和当前贪心策略会选择的元素逐个交换后得到的解A’并不比
A差（假设贪心策略会选择的元素在当前最优解中未被选择，通过“剪切-粘贴”证明得到的仍是最优解），可以证明存在原问题的最优解可以通过贪心选择得到。
5.动态规划
5.1 算法思路
把多阶段过程转化为一系列单阶段问题，并利用各阶段之间的关系逐个求解。
5.2 从穷举角度看动态规划
以下摘自《labuladong的算法小抄》
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
列出状态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。
备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？
5.3 适用范围
①最优化原理（最优子结构性质）
问题的最优解所包含的子问题的解也是最优的
②无后效性
某阶段的状态一旦确定，就不受这个状态以后决策的影响。
③有重叠子问题
子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
5.4 算法框架
# 初始化 base case dp[0][0][...] = base # 进行状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for ... dp[状态1][状态2][...] = 求最值(选择1，选择2...)
5.5 三种常用思路(解题步骤)
下述思路往往是递进的关系
①暴力递归
暴力递归可不简单，要想暴力递归出解法，首先得知道状态转移方程
状态转移方程是用于前后阶段关系的
如何列出正确的状态转移方程？
1、确定 base case
2、确定「状态」，也就是原问题和子问题中会变化的变量
3、确定「选择」，也就是导致「状态」产生变化的行为
4、明确 dp 函数/数组的定义。
明确上述几点后，我们就能根据其写出状态转移方程，根据状态转移方程我们也就能很快写出对应的递归代码。
②带备忘录的递归
由于重叠子问题的存在，暴力递归的效率往往很低，原因在于会重复对某些状态进行递归。因此我们自然而然就想到可以通过备忘录的形式把每个状态的值记录下来，等下次再用到的时候就不用大费周章再去递归一遍，而是直接拿。
很显然「备忘录」大大减小了子问题数目，完全消除了子问题的冗余，做到了“聪明的穷举”。
③dp 数组的迭代解法
dp 数组的迭代解法和递归的思路很像，也是需要一个dp数组来记录状态，不过递归解法往往是一个自上而下的过程，而它是自下而上层层迭代的过程——由先前的状态迭代往后得出后面的状态。
这种自下而上的思路往往不符合人的惯性思维，解题时往往要搞清楚状态之间的先后关系，必须先遍历初始的状态，再根据状态慢慢演变得出后续的状态，在得到答案之前，它需要遍历所有状态。
当然这种解法往往存在一种技巧——状态压缩（或者叫做滚动数组），如果计算状态 dp[i][j] 需要的都是 dp[i][j] 相邻的状态，那么就可以使用状态压缩技巧，将二维的 dp 数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。
总结
递归写法往往更符合人的思考方式，可以更容易写出答案，自上而下的解法可以只对需要的状态求解，在一定程度上提高效率。
dp数组的迭代解法是一种自下而上的解题思路，需要明确状态的先后关系，往往不太符合人的思考方式，得到答案之前需要遍历所有状态。不过它可以用状态压缩/滚动数组的技巧来降低空间复杂度。
在解动态规划问题时，我们可以先从暴力递归入手，逐步去优化写出最终的答案，一般写到带备忘录的递归即可。
6.概率算法
6.1 数值概率算法
常用于解决数值计算的问题。该算法往往只能得到问题的近似解，并且该计算解的精度一般随着计算时间的增加而不断提高。
6.2 蒙特卡罗算法
蒙特卡罗算法用于求问题的准确解。蒙特卡洛算法1945年由冯诺依曼行核武模拟提出的。它是以概率和统计的理论与方法为基础的一种数值计算方法，它是双重近似：一是用概率模型模拟近似的数值计算，二是用伪随机数模拟真正的随机变量的样本。
当所求解问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某种“实验”的方法，以这种事件出现的频率估计这一随机事件的概率，或者得到这个随机变量的某些数字特征，并将其作为问题的解。
蒙特卡罗算法能求得问题的一个解，但这个解未必是正确的。求得正确解的概率依赖于算法所用的时间。算法所用的时间越多，得到正确解的概率就越高。蒙特卡罗算法的主要缺点就在于此。一般情况下，无法有效判断得到的解是否肯定正确。
示例问题：根据伪随机数求π
6.3 拉斯维加斯算法
拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。
示例问题：求解n皇后
6.4 舍德伍算法
舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。
四、计算复杂性理论
1.图灵机模型
图灵机是一种数学计算模型，它定义了一个抽象机器，该抽象机器根据规则表来操纵带子上的符号。尽管该模型很简单，但是在任何给定计算机算法的情况下，都可以构建出模拟该算法逻辑的图灵机。
简单点说，图灵机就是一个模拟算法运行的抽象机器。它是这样定义的：
有一个无限长度的磁带，这个磁带被分成了一个接一个的单元格，磁带被用于写入字母和符号。
一个读写磁带的磁头，这个磁头负责控制堆磁带的写入和左右移动。
一个状态寄存器，用来存储图灵机的状态。
一个指令表，可以根据机器当前所处的状态和磁带上当前的符号，指示机器进行特定的操作。比如：擦除或者写入一个符号、向左或者向右移动磁头。
①确定图灵机
在确定性图灵机（DTM）中，其控制规则规定了在任何给定情况下最多只能执行一个动作。
确定性图灵机具有转换功能，对于磁带头下的给定状态和符号，该转换功能指定了三件事：
要写入磁带的符号，头部应移动的方向（向左，向右或都不向），以及有限控制的后续状态。
例如，状态3的磁带上的X可能会使DTM在磁带上写Y，将磁头向右移动一个位置，然后切换到状态5。
①非确定图灵机
在理论计算机科学中，非确定性图灵机（NTM）是一种理论计算模型，其控制规则在某些给定情况下指定了多个可能的动作。 也就是说，NTM的下一个状态不是完全由其动作和它所看到的当前符号决定的（不同于确定性图灵机）。
3.P、NP、NPC类问题
P问题：有多项式时间算法，算得很快的问题。
NP问题：算起来不确定快不快的问题，但是我们能在多项式时间内验证得出一个正确解的问题
NP-complete问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。
NP-hard问题：比NP问题都要难的问题。
