| 这个问题来自 Quora ，下面是 Brian Bi 的回复，2200+ 赞，由严伟翻译。
动态规划（DP）似乎占据了大部分的竞赛题目（有估计说占了三分之一）。当然，DP也不是一个学一次就Ok的单一算法，所以，也许这并没有回答你的问题。 我想这还取决于你是否把数据结构与算法放在同一个等级中考虑。如果你想要在编程竞赛中一展风采的话，当然，有些数据结构是你应该熟悉的。其中最重要 的有范围树（Range Tree，也被称为线段树或区间树）和树状数组（BITs），也被称作Fenwick树。除此之外，许多DP算法使用了一个前缀和数组（prefix sum array）。 我能想到的最精华的单一算法如下所列，排名不分先后。然而，你可能会因为这其中的一些算法在真正的竞赛中很少出现而感到失望。绝大多数非动态规划问题似乎都是各种ad hoc网络与数据结构，所以你只需要练习练习以熟练掌握它们。 （再一次声明，我仅列出了满足如下性质的算法：有单一输入集；计算输入集的某个函数；不携带输入值之间的状态。这些性质将下面的算法与数据结构区分开来。由定义，数据结构要保留状态以及算法的等级，还有像是DP这样的算法技术，它们并没有前者所计算的某个具体函数。） 1.Eratosthenes筛法，或另一种素数筛法 2.深度优先搜索 3.广度优先搜索 4.Dijkstra算法 5.Floyd–Warshall 算法 6.Either Kruskal算法 或称 Prim算法 7.一些拓扑排序的实现，比如使用DFS 8.凸包（我推荐单调链算法） 9.坐标压缩 10.Edmonds–Karp，或者Ford–Fulkerson方法的另一种实现；亦或预流推进算法；又或者，如果你在准备ACM codebook，那么就Dinic算法。（注意：最大流不允许出现在国际资讯赛中，尽管如此，它也可能会出现在国家队选拔赛中。） 其他回复，可见 Quora 原帖。 |
