算法策略

贪心算法

一个贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。

确定贪心策略 选择当前看上去最好的方案

一步一步得到局部最优解

将所有局部最优解合并称为一个原来问题的最优解

原则

选择一个最好的贪心策略

物品可分割称为背包问题 物品不可分割称为0-1背包问题

递推法

由当前问题的逐步解决从而得到整个问题的解，只是依赖的是信息间本身的递推关系

递归法

解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法

特别地，当规模N=1时，能直接得解

写递归代码最关键的是写出递推公式，找到终止条件。实现递归代码要注意的两个问题：调用栈溢出与重复计算

枚举法

对所有可能的解逐一尝试，从而找出问题的真正解

这就要求所解的问题可能的解是有限的、固定的，不会产生组合爆炸、容易枚举的

分治法

其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题，分而治之, 递归地求解问题

每层递归应用：

对于递归的问题，当不需要再继续递归分解子问题时，就是一个基本情况，此时可直接得出解，否则就是递归情况

递归式则可以用来描述复杂度，如归并排序的递归式

O(1)           若 n = 1
2T(n/2) + O(n) 若 n > 1

分治算法要素

典型算法

动态规划

通过子问题的最优解，推导出最终问题的最优解，把这些子问题之间的转移称为状态转移，并把用于刻画这些状态转移的表达式称为状态转移方程

基础

动态规划的思想类似于分治法

不过动态规划是从最小子问题求起 将小问题的解存储起来

求解大问题时 如果需要用到小问题的解 直接使用即可 无需再重复计算

要素

典型算法

回溯法

回溯法是一种选优搜索法，按照选优条件深度优先搜索，以达到目标。当搜索到某一步时，发现原先选择并不是最优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态称为“回溯点”。

要素

典型算法

分支限界法

回溯法找出所有解

分支限界法找出一个接

回溯法深度优先 分支限界法广度优先

回溯法搜索一次生成一个孩子节点 分支限界法一次生成所有节点

线性规划网络流

解决

算法思想

数据结构决定程序

使用更合适的数据结构能减少代码量

正确的程序

性能分析

估算

使用小实验获取关键参数

任何事都应尽量简单 但不宜过于简单

算法设计

代码调优

一些优化方案：

节省空间

自描述数据

技巧