本次机考时长 \(90 min\) ，共 \(5\) 题，难度大致为普及。采用学校内部 OJ 进行判题，题目只提供纸质版，OJ 中只做提交。排名以 ACM 标准为主，若过题数为零则参考部分分。
第六讲-图论基础、数学与计算几何
第五讲-数据结构与字符串
动态规划
发表于
本文字数： 10k 阅读时长 ≈ 9 分钟
本文字数： 10k 阅读时长 ≈ 9 分钟
动态规划
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
当问题具有最优子结构并且可以使用自底向上方法解决时，使用动态规划。动态规划方法通过两种技术(记忆和制表)扩展了分而治之的方法，这两种技术都具有存储和重用子问题解决方案的目的，可以极大地提高性能。例如，斐波那契函数的朴素递归实现的时间复杂度为 \(O(2^n)\)，而 DP 解决方案只需要 \(O(n)\) 时间就可以完成同样的工作。
第四讲-动态规划与背包思想
第三讲-贪心、模拟与二分
第二讲-搜索与优化
CS 自学资源
算法学习资源导航