基本原理

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

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

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

总的来说,动态规划的优势在于:

步骤

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

HDU

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

  2. http://acm.hdu.edu.cn/showproblem.php?pid=1003 hdu1003 参考答案

  3. http://acm.hdu.edu.cn/showproblem.php?pid=1087 hdu1087 参考答案

  4. http://acm.hdu.edu.cn/showproblem.php?pid=1159 hdu1159 参考答案

  5. http://acm.hdu.edu.cn/showproblem.php?pid=1176 hdu1176 参考答案

  6. http://acm.hdu.edu.cn/showproblem.php?pid=1058 hdu1058 参考答案

  7. http://acm.hdu.edu.cn/showproblem.php?pid=1069 hdu1069 参考答案

  8. http://acm.hdu.edu.cn/showproblem.php?pid=2059 hdu2059 参考答案

  9. http://acm.hdu.edu.cn/showproblem.php?pid=2084 hdu2084 参考答案

  10. http://acm.hdu.edu.cn/showproblem.php?pid=1024 hdu1024 参考答案

动态规划典型例题

参考资料

动态规划练习

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

算法专题:动态规划 (last edited 2008-10-22 14:50:24 by 218)

ch3n2k.com | Copyright (c) 2008 czk. 浙ICP备06000584号