算法策略
分治法
特征:把一个问题拆分成多个小规模的相同子问题,一般可用递归解决
经典问题:斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔
贪心法
特征:局部最优,但整体不见得最优。每步有明确的、既定的策略。
经典问题:背包问题(如装箱)、多机调度、找零钱问题、最小生成树问题
部分背包可以得到最优解,0-1背包不一定是最优解
动态规划法(用于求解最优解)
特征:划分子问题,使用数组存储子问题,利用查询子问题结果构造最终问题结果。使用最优子结构+递归式
经典问题:斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列
回溯法
特征:系统地搜索一个问题的所有解或任一解,是一种选优搜索法,按选优条件先前搜索,以达到目标。但当搜索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。这种走不通就退回再走的技术就是回溯法
经典问题:N皇后问题、迷宫、背包问题