动态规划基础和建模
第一页，共105页
动态规划是统筹学的重要内容
动态规划是OI的重要内容
据不完全统计，每次考试动态规划起码有一道题
前言
动态规划很重要 ！
第二页，共105页
这个课件的目的：
对动态规划的模型进行了一些总结
有部分内容超出了NOIP范围
为同学们提供一个刷题的方向
请同学们踊跃发言
前言
第三页，共105页
阶段
状态
决策
状态转移
状态转移方程
动态规划的基本概念
第四页，共105页
最优子结构
无后效性原则
重叠子问题
动态规划的基本概念
DP是一种记忆化的思想
第五页，共105页
拓展一下：
阶段 -> 拓扑序
状态 -> 点
状态转移 -> 边
决策 -> 前驱？DFA？
动态规划的基本概念
DP是状态空间上的最短（长）路或者可行路
第六页，共105页
实现方式：
递推：顺推和逆推
记忆化搜索
前者灵活，优化方法多
后者可以减少不必要节点的计算
动态规划的基本概念
第七页，共105页
时间复杂度：
状态数*转移费用
动态规划的基本概念
第八页，共105页
线性模型
区间模型
矩形模型
树形模型
背包模型
图状模型
SCDP
多线程DP
多重DP
更广泛的
动态规划的模型
第九页，共105页
单线问题：
上楼梯问题
LIS问题
乌龟棋
诗人小G（简化版）
双线问题：
LCS问题
模糊匹配
线性模型
第十页，共105页
动态规划基础和建模 来自淘豆网m.daumloan.com转载请标明出处.
