17121
备注:
|
17231
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 18: | 行号 18: |
* ["hdu1466 参考答案"] ''' 计算直线的交点数''' DP * ["hdu1003 参考答案"] ''' 最大子段和''' 经典DP * ["hdu1087 参考答案"] ''' Super Jumping! Jumping! Jumping!''' 经典DP:严格递增子列最大和 * ["hdu1159 参考答案"] '''Common Subsequence''' 经典DP:LCS,最长公共子列 * ["hdu1176 参考答案"] ''' 免费馅饼''' DP * ["hdu1058 参考答案"] ''' Humble Numbers''' DP * ["hdu1069 参考答案"] ''' Monkey and Banana''' DP * ["hdu2059 参考答案"] ''' 龟兔赛跑''' DP * ["hdu2084 参考答案"] ''' 数塔''' DP |
1. http://acm.hdu.edu.cn/showproblem.php?pid=1466 [[hdu1466 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1003 [[hdu1003 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1087 [[hdu1087 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1159 [[hdu1159 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1176 [[hdu1176 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1058 [[hdu1058 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=1069 [[hdu1069 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=2059 [[hdu2059 参考答案]] * http://acm.hdu.edu.cn/showproblem.php?pid=2084 [[hdu2084 参考答案]] |
基本原理
动态规划是最优化原理中的一种重要的方法。
动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决。
总的来说,动态规划的优势在于:
- 重叠子问题
- 最优子结构
- 记忆化
步骤
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态 规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表 格中简单地查看一下结果,从而获得较高的效率。
HDU
动态规划典型例题
- 最长单调子序列
- Floyd-Warshall算法
参考资料
动态规划练习
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