算法基础

如何进行动态规划，没有一定之规，需要具体问题具体分析。本模块首先由典型的“最长上升子序列”引入，进一步展示几个较难的动规例题，深入探讨动态规划算法中状态的设计以及状态转移关系的构建。

想象我们在一座迷宫里，如何才能找到出口呢？最直观的方法是从入口开始沿着一条路一直走到底，如果遇到分叉路口就选择其中一条道路走下去，如果遇到死胡同就退回到上一个分叉路口，选择另一条道路走下去，如果遇到出口就成功走出迷宫了。这种尽量往深处走的做法即是深度优先搜索(深搜）。深搜算法编程简单，简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，如果不加以优化，时间效率无法忍受。本模块将通过实例继续讨论深度优先搜索算法中优化程序的基本方法“剪枝”，即在设计剪枝判断方法的基础上，避免一些不必要的遍历过程，从而提高算法效率。

本模块继续通过两道例题，强调了两种最通用的剪枝方法：可行性剪枝和最优性剪枝的应用。可行性剪枝即在寻找解的过程中，预判出从当前状态出发不可能找到解，从而不再从当前状态继续；最优性剪枝就是记录到目前为止找到的最优解，当发现正在探索的解其代价已经不小于最优解，或预测出其最终代价必将不小于最优解，则停止当前解的探索。

与深度优先搜索算法类似，广度优先搜索(广搜)也是常用的搜索图的算法。它的思想是从一个顶点开始，辐射状地优先遍历其周围较广的区域。一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法都是基于广搜的思想。广索的基本方法是使用队列存放已经扩展过的节点。本模块先以简单例题引入广搜的基本实现方法，然后再通过经典的"八数码"问题，进一步介绍状态表示、判重的节省时间和空间的技巧。

二分法是在有序或单调的区间中快速寻找答案的有效方法，当数据量很大适宜采用该方法。所谓贪心算法，即总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。但是，贪心算法对很多问题都能得到整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。本模块将介绍二分与贪心这两个对很多问题都非常有效的算法策略。

3个小时11道题目，这就是每年我们程序设计实习课程在校内的收官之作，让无数北大学生魂牵梦绕又各种怨念纠结的期末盛宴。你是不是准备好了呢？快来测测吧！也别忘了，搞定了基本算法并不代表着你作为程序员所向披靡啦，毕竟好的 程序=数据结构+算法。快去参加张铭老师的《数据结构基础》吧，你值得拥有！

真的要把课程的接力棒传给张老师了，颇有些不舍！很高兴通过MOOC专项课程的方式结识不一样的你。希望我们的课程能带给你收获与思考，加油，你会是一位出色的程序员！