算法

• 基础算法

  • 模拟

  模拟仅需理解清楚题意，然后按照题意列出所有情况模拟即可。关键点在于理解清楚题目意思，能够整理出所有情况并正确处理，考察代码编写能力。在某一些模拟题中，可以利用状态机来维护状态，简化代码逻辑。

  • 贪心

    贪心算法指每次都选择当前的最优解，所以当使用贪心算法时，需要确保贪心是正确的解法。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

    在证明时，通常使用反证法和归纳法，这样能保证贪心算法的正确性，也能防止自己错误的使用了贪心算法。

• 数据结构（详细查看数据结构相关内容）

  • 链表
  • 栈
  • 队列
  • 堆

• 树

• 搜索

  • dfs

    dfs是一种搜索算法，主要依靠递归来实现，也可以利用栈来模拟。该类搜索算法的特点在于，将要搜索的目标分成若干“层”，每层基于前几层的状态进行决策，直到达到目标状态。例如：将一个整数分解成m个整数，输出所有可能性，这便可以定义一个方法叫做split，带上一个参数n代表原先整数，一个参数m代表分解成m个整数，之后在split中调用自己（split(n-i,m-1)）直到第二个参数为0时print出当前的结果，整个代码也就是dfs的过程。

  • bfs

    bfs和dfs有所不同，dfs是不断往一个方向走，走到不能走后返回上一步；而bfs则是在一个点上先探索所有可能性，然后将所有可能性放入队列中，再从队列中取出一个可能性继续搜索，直到搜索到符合答案的结果或者队列为空时停止。最经典的使用便是在所有道路长度为1时，找到从n点到m点的最短路或最长路，也可以利用bfs找到迷宫的出口。

  • 启发式

    启发式搜索是一种改进的搜索算法。它在普通搜索算法的基础上引入了启发式函数，该函数的作用是基于已有的信息对搜索的每一个分支选择都做估价，进而选择分支。简单来说，启发式搜索就是对取和不取都做分析，从中选取更优解或删去无效解。

• 动态规划

  • 基础

    动态规划应用于子问题重叠的情况：

    1. 要去刻画最优解的结构特征；
    2. 尝试递归地定义最优解的值（就是我们常说的考虑从i-1转移到i）；
    3. 计算最优解；
    4. 利用计算出的信息构造一个最优解。

  • 背包

    • 01背包
    • 完全背包

  • 树形

  • 状压

  • 区间

• 刷题网站

  • www.luogu.com.cn
  • leetcode-cn.com
  • acm.hdu.edu.cn
  • vjudge.cn