算法专题：动态规划

返回“算法” · 返回“大学生程序设计竞赛”

基本原理

动态规划是最优化原理中的一种重要的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决。

总的来说，动态规划的优势在于：

  • 重叠子问题
  • 最优子结构
  • 记忆化

步骤

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态 规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表 格中简单地查看一下结果，从而获得较高的效率。

HDU

  1. http://acm.hdu.edu.cn/showproblem.php?pid=1466 hdu1466 参考答案

动态规划典型例题

参考资料

动态规划练习

Vol I

Vol II

Vol III

Vol IV

Vol V

Vol VI

Vol VII

Vol VIII

Vol IX

Vol X 1913 by javaman

Vol XI

Vol XII

Vol XIII

Vol XIV

Vol XV

Vol XVI 2501 by Vegetable Bird

Vol XVII

Vol XVIII