经典总结别人最优算法大全

1、一维线性dp：每次考虑i时，选择最优子问题要么在i-1，要么在1...i-1里；
2、二维线性dp：考虑(i,j)子问题时，选择最优子问题要么在(i+1,j)、(i,j-1)，要么在i<= k <=j，在k里；
3、树形dp：考虑i节点最优时，选择子节点最优，一般融合了01背包dp的双重dp。



图论 
           拓扑排序 
               有向无环图与动态规划的关系

       二分图匹配问题 
           一般图问题与二分图问题的转换思路 
           最大匹配 
               有向图的最小路径覆盖 （把总点数-最大匹配数)
               0 / 1矩阵的最小覆盖 
           完备匹配  (匈牙得算法)
           最优匹配  (KM算法)
           稳定婚姻 

       网络流问题 
           网络流模型的简单特征和与线性规划的关系 
           最大流最小割定理 
           最大流问题 
               有上下界的最大流问题 
                   循环流 
           最小费用最大流 / 最大费用最大流

       弦图的性质和判定

组合数学

       解决组合数学问题时常用的思想 
           逼近 
           递推 / 动态规划 
       概率问题 
           Polya定理


计算几何 / 解析几何

       计算几何的核心：叉积 / 面积 
       解析几何的主力：复数

       基本形 
           点 
           直线，线段 
           多边形

       凸多边形 / 凸包 
           凸包算法的引进，卷包裹法

       Graham扫描法 
           水平序的引进，共线凸包的补丁

       完美凸包算法

       相关判定 
           两直线相交 
           两线段相交