动态规划.ppt

文档介绍：动态规划
动态规划的含义
规划?
静态规划?
动态规划
动态规划解决什么样的问题
有些问题明显具有某些结论
能够使用动态规划的两个前提条件
无后效性
最优化原理
经典问题
最长上升序列(LIS)
乘法问题
数塔问题
区间选择与加权区间选择
最小代价子母树
最长上升序列
5 4 6 2 9 3 5 8 7 10
5 4 6 2 9 3 5 8 7 10
5 4 6 2 9 3 5 8 7 10
5 4 6 2 9 3 5 8 7
f[i]表示以第i个数结尾可以获得的最长上升序列
状态?阶段?决策?
状态转移方程?
补充
对LIS的O(nlogn)的算法的理解
乘法问题
310143 4份
3*10*14*3=1260
3*101*4*3=3636
310*1*4*3=3720
???????*3
3*10*1*43 ?
??????*43
状态:f[i,j]表示前i个分成j部分
阶段?
数塔问题
松弛操作?
图论中最短路算法的理论依据
7
3 8
8 1 0
2 7 7 4
4 5 2 6 5
区间选择
贪心
按结束位置排序
可以选就选
正确性?
带权?还正确吗?
加权区间选择
结束点排序
状态:所有结束点
决策:选?不选?
选:Vi+best[?]
不选:best[?]