DP动态规划PPT学习教案

1、会计学1DP动态规划动态规划第1页/共74页第2页/共74页第3页/共74页第4页/共74页者最大者最大.第5页/共74页第6页/共74页第7页/共74页记忆化的功效第8页/共74页第9页/共74页第10页/共74页第11页/共74页显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。第12页/共74页第13页/共74页第14页/共74页第15页/共74页第16页/共74页2 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 状态的表示

2、状态的表示fi,jfi,j表示前表示前i i个第一排的数字和前个第一排的数字和前j j个第二排的数字搭配的最优值。个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错的后面两个位置当前的状态就是当前你枚举到的一组交错的后面两个位置. .例如上图中当前状态是例如上图中当前状态是3 3和和1(1(第一组交错第一组交错),),枚举他的以前状态就有枚举他的以前状态就有1 3.1 3.这样在这样在1 31 3之前会有一个最优值存在之前会有一个最优值存在, ,因此可以由此得到因此可以由此得到3 13 1的最优值的最优值. .第17页/共74页号为号为N N。第18页/共74页第19页/共74页

3、怎么怎么办办第20页/共74页当前所在的某个车站这一题的以前状态其实只有这一题的以前状态其实只有3种种.即满足即满足3种距离种距离(收费收费)情况的情况的3个车站个车站.要知道这要知道这3个车站可以先做一个预处理个车站可以先做一个预处理.显然这显然这3个车站在满足距离限制的条件下应该越远越好个车站在满足距离限制的条件下应该越远越好.第21页/共74页第22页/共74页第23页/共74页第24页/共74页第25页/共74页第26页/共74页第27页/共74页第28页/共74页或许你不明白我在说什么,那么我们通过题目来说明吧第29页/共74页第30页/共74页后后,乘积最大的一题也是乘积最大的一题

4、也是完全一样的形式完全一样的形式,谁还会谁还会去用搜索去用搜索?第31页/共74页第32页/共74页第33页/共74页寻找定量!第34页/共74页第35页/共74页第36页/共74页第37页/共74页第38页/共74页第39页/共74页第40页/共74页定量很不错啊!第41页/共74页第42页/共74页第43页/共74页第44页/共74页第45页/共74页第46页/共74页对于所给出的矩阵找出一条最长的递减链,满足链中相邻的两个元素间都是在矩阵中相邻的.上图中所给出的矩阵中的最长链是1 2 3 425.第47页/共74页第48页/共74页第49页/共74页第50页/共74页第51页/共74页第

5、52页/共74页|讲完了比较实用的两种种动规的武器之后,我们来看看一些大家可能不太会做的动规类型第53页/共74页第54页/共74页第55页/共74页第56页/共74页第第i个房间个房间.用用fi,j来表来表示示.第57页/共74页K表示的是和I连接的一个房间,ci表示进入I号房间的花费.第58页/共74页会的总活跃指数最大。会的总活跃指数最大。第59页/共74页第60页/共74页j,0),j为为i的的i儿子）。儿子）。n这就是树状动规的基这就是树状动规的基本形态。本形态。第61页/共74页第62页/共74页第63页/共74页最小的结点有哪些。最小的结点有哪些。如有多个最小的如有多个最小的Ai，则都要输出。这里则都要输出。这里N=10000N=10000第64页/共74页