神马文学网动态规划详解 第二章 - C/C++教学资料区 - 飞燕之家在线测评论坛OnlineJud...
来源：百度文库 编辑：神马文学网 时间：2024/04/28 03:08:44
动态规划详解 第二章
通过上一章的学习，相信大家对动态规划已经有了一个初步的了解，如果您将上一章的推荐习题全部掌握，那么您可以开始这一章的学习内容了。
这一章，我们将讲解一些动态规划的设计技巧。
相信大家在做动态规划一类题目的时候，往往不容易看出来这道题目是动态规划。其实这并不是您的IQ低，几乎所有的初学者都会存在这样的问题，我同样也不例外，不过凭借我超人的天赋，终于总结出来如何看出来某道题是不是动态规划的终极方法：
做题做题在做题！在一年半的学习中，我深刻的体会到了：动态规划是做出来的！这个硬道理，没有题目数量的保证，学好动态规划是很困难的。
但是动态规划也并非是无章可循，下面就为大家介绍几种常见的类型：
1．极值问题
这类问题的显著特征就是让您求出最X值，并且往往具有最后子结构的性质，因为其模型变化丰富，并且和实际联系紧密，所以在动态规划类问题中占有很大的重量
2．总数问题
3．一类博弈问题
4．某些杂题
一般情况下，动态规划类的问题往往就这几种类型，因此当大家看到以上几种类型的时候，不妨向动态规划的方向作些思考。
学习动态规划的另一个难点就是状态的设计，可以说，只要有了状态，那么决策和阶段也就迎刃而解了。
一个好的状态，首先要把问题描述清楚，其次转移的时候应当尽量“简单”，这里的简单，主要指状态之间的“距离”，譬如A[I]=MAX(A[J]) J<=I就没有A[I]=A[I-1]好。
下面让我们看一道题目：
例：排队买票
问题描述：一场演唱会即将举行。现有N（O〈N〈=200〉个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第I位歌迷买一张票需要时间Ti（1〈=I〈=n〉，队伍中相邻的两位歌迷（第j个人和第j+1个人）可以由前一个人买两张票，也可由后一位买两张票，则另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，现给出N，Tj和Rj，求使每个人都买到票的最短时间和方法。
因为可以从前一个人买票，又可以从后一个人买票，似乎不符合无后效性的原则，没有办法用动态规划求解。
所以我们不妨采用加一维的策略：
设F（I，**）为到第i个人为止所需的最短时间.
设Ti为第I个人单独买票的时间。
设 Ri为第I个人买2张票的时间。
则：状态转移方程分5种情况：
F（I，仅买1张）=MIN{F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}+Ti
F（I，买2张代前一位）=MIN{F（I-2，仅买1张），F（I-2，买2张代前一位），F（I-2，不买由前代）}+Ri
F（I，买2张代后一位）=MIN{F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}+Ri
F（I，不买由前代）= F（I-1，买2张代后一位）
F（I，不买由后代）=MIN{ F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}
注：本题的状态还可以继续优化到3种，请大家自己思考。
从上面的例子我们可以看到，当遇到题目的状态无论如何也无法免除后效形时，可以采用加一维的方法来解决，有的时候甚至需要加两维甚至三维。
处理动态规划时还有几种技巧：
1．对于一些需要计算出权函数的题目，不妨把函数的计算放置到动态规划之外，同时还可以尝试对一些权函数进行合并，这类处理权函数的技巧还有很多，相信大家在做题的过程中都会遇到，就不再详细展开了
2．对于某些状态，不妨对约束条件加以宽松，往往会起到出其不意的效果。
3．可以采用循环数组技术，比较经典的应用就是上一章的数字三角形，因为只和上一层的状态有关，和其他的状态无关，所以不妨只保存上一层的结果，每次计算出新的结果后就把上一层的结果舍弃，这样会让空间复杂度大大降低，是非常有用的一种优化方法。
4．采用状态压缩技术，这个优化的应用较为复杂，变形很多，有兴趣的不妨在网上查找相关资料
<<<<<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>>>>>>>>
通过上一章的学习，相信大家对动态规划已经有了一个初步的了解，如果您将上一章的推荐习题全部掌握，那么您可以开始这一章的学习内容了。
这一章，我们将讲解一些动态规划的设计技巧。
相信大家在做动态规划一类题目的时候，往往不容易看出来这道题目是动态规划。其实这并不是您的IQ低，几乎所有的初学者都会存在这样的问题，我同样也不例外，不过凭借我超人的天赋，终于总结出来如何看出来某道题是不是动态规划的终极方法：
做题做题在做题！在一年半的学习中，我深刻的体会到了：动态规划是做出来的！这个硬道理，没有题目数量的保证，学好动态规划是很困难的。
但是动态规划也并非是无章可循，下面就为大家介绍几种常见的类型：
1．极值问题
这类问题的显著特征就是让您求出最X值，并且往往具有最后子结构的性质，因为其模型变化丰富，并且和实际联系紧密，所以在动态规划类问题中占有很大的重量
2．总数问题
3．一类博弈问题
4．某些杂题
一般情况下，动态规划类的问题往往就这几种类型，因此当大家看到以上几种类型的时候，不妨向动态规划的方向作些思考。
学习动态规划的另一个难点就是状态的设计，可以说，只要有了状态，那么决策和阶段也就迎刃而解了。
一个好的状态，首先要把问题描述清楚，其次转移的时候应当尽量“简单”，这里的简单，主要指状态之间的“距离”，譬如A[I]=MAX(A[J]) J<=I就没有A[I]=A[I-1]好。
下面让我们看一道题目：
例：排队买票
问题描述：一场演唱会即将举行。现有N（O〈N〈=200〉个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第I位歌迷买一张票需要时间Ti（1〈=I〈=n〉，队伍中相邻的两位歌迷（第j个人和第j+1个人）可以由前一个人买两张票，也可由后一位买两张票，则另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，现给出N，Tj和Rj，求使每个人都买到票的最短时间和方法。
因为可以从前一个人买票，又可以从后一个人买票，似乎不符合无后效性的原则，没有办法用动态规划求解。
所以我们不妨采用加一维的策略：
设F（I，**）为到第i个人为止所需的最短时间.
设Ti为第I个人单独买票的时间。
设 Ri为第I个人买2张票的时间。
则：状态转移方程分5种情况：
F（I，仅买1张）=MIN{F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}+Ti
F（I，买2张代前一位）=MIN{F（I-2，仅买1张），F（I-2，买2张代前一位），F（I-2，不买由前代）}+Ri
F（I，买2张代后一位）=MIN{F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}+Ri
F（I，不买由前代）= F（I-1，买2张代后一位）
F（I，不买由后代）=MIN{ F（I-1，仅买1张），F（I-1，买2张代前一位），F（I-1，不买由前代）}
注：本题的状态还可以继续优化到3种，请大家自己思考。
从上面的例子我们可以看到，当遇到题目的状态无论如何也无法免除后效形时，可以采用加一维的方法来解决，有的时候甚至需要加两维甚至三维。
处理动态规划时还有几种技巧：
1．对于一些需要计算出权函数的题目，不妨把函数的计算放置到动态规划之外，同时还可以尝试对一些权函数进行合并，这类处理权函数的技巧还有很多，相信大家在做题的过程中都会遇到，就不再详细展开了
2．对于某些状态，不妨对约束条件加以宽松，往往会起到出其不意的效果。
3．可以采用循环数组技术，比较经典的应用就是上一章的数字三角形，因为只和上一层的状态有关，和其他的状态无关，所以不妨只保存上一层的结果，每次计算出新的结果后就把上一层的结果舍弃，这样会让空间复杂度大大降低，是非常有用的一种优化方法。
4．采用状态压缩技术，这个优化的应用较为复杂，变形很多，有兴趣的不妨在网上查找相关资料
<<<<<<<<<<<<<<<<<<<
动态规划详解 第二章 - C/C++教学资料区 - 飞燕之家在线测评论坛OnlineJud...
动态规划详解 第一章 - C/C++教学资料区 - 飞燕之家在线测评论坛OnlineJud...
C程序设计 第二版 视频教学
c菜肴之家
动态鲜花图片c
C语言第二摘
《千字文》详解C
L/C操作详解
感受“天使”的魅力-百诺C-1691EX碳纤脚架试用 - 器材测评 - 佳友在线摄影网
不动如山 体验新一代百诺C-257M8三脚架套装 - 器材测评 - 佳友在线摄影网
入门教程：实例详解C 1
c#socket发送邮件详解
C中的ComBox控件详解
中国之最c
JSTL之c标签
Linux上的C/C 编译器gcc/egcs详解
Linux上的C/C 编译器gcc/egcs详解
【测评】我手中的NEX-5C微单测评体验 - 索尼 - 搜狐数码公社
（C）身材也可以玩规划？
C语言调用Dll动态链接库
老英雄的无悔人生[组图]! ! ! - 我爱涪陵 - 涪陵在线-涪风论坛 FuLing.C...
c/c++程序之_KMP字符串模式匹配详解 - A_B_C_ABC欢迎你 - CSDN博客
入门教程：实例详解C 友元2
入门教程：实例详解C 友元3