动态规划基础.

动态规划基础——HadesDP的动机•1、递归时产生了大量的重叠子问题•F[n]=F[n-1]+F[n-2]•2、问题可以看成一种多阶段决策过程DP四部曲1、设状态2、分阶段3、求状态转移方程4、计算边界什么是状态？•整个过程中，每一个拥有不同决策的现状个体。什么是阶段？•没有依赖关系（或平行）的状态的集合称之为阶段状态转移•对于某个状态，通过一个决策使之转化为另外一个状态，则称之为状态转移。状态转移方程•对于任何一个状态，用一个递推方程来表示其转移的代价边界•即递推的边界，或者初始值DP的必要条件•1、具有最优子结构•2、无后效性最优子结构•设一个状态t，所有可以通过决策转化为t的状态集合设为S那么t的最优决策必定是S中的某个决策无后效性•对于两个状态，其转移必须只能是单向的•如果对于两个状态A,B，通过决策可以使得A,B互相转化，则称其有后效性。DP解题的方法•1、DP基本流程•2、经典模型–线性DP（1D/1D动态规划）–区间DP–资源分配DP–树形DP–概率DP–多进程DP–数位DP–插头DP例题一：数字三角形•有一个N层的三角形数字塔，第i行有i个数字。假设你站在第一行，一直往下走，每次可以走左边也可以走右边每走到一个点就可以拿起这个点上的数字作为分数。求走到最下层之后的最大的分•右图为n=5的情况。12223464787494212479一、设状态整个问题就是从第一行走到最后一行，那么我处在不同的位置，就会有不同的决策。所以此题中的状态就是我所在的位置。用（i，j）表示。122234647874942二、分阶段•显然，某一层的状态之间不存在任何转移关系，可以认为是平行的，所以每一层就是一个阶段。122234647874942三、写状态转移方程]][[]1][1[]][1[max]][[jiajifjifjif•对于某个状态（i，j），他只有可能从（i-1，j）和（i-1，j-1）这两个状态转移过来。•那么我们令f[i][j]表示走到（i，j）这个状态时可以取到的最大值•若是从左边过来的，就有f[i][j]=a[i][j]+f[i-1][j-1]•若从右边过来，就有f[i][j]=a[i][j]+f[i-1][j]•写成一个式子，就是:四、计算边界•此题求解实际上是一个递推的过程，那么我要确定所有递推的起点，也就是•f[1][1]=a[1][1]f[0][i]=-∞f[i][0]=-∞f[i][i+1]=-∞•其中1=i=n•如果题目保证数据非负，也可以把-∞改成0思考题–数字三角形改版1–把得分最大改为得分对100取模之后最大–数字三角形改版2–把题目改成从下往上走，走到顶端后再从上往下走到底，使得经过的数字总和最大（重复经过的点只算一次）线性动态规划•给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质，s1s2s3...sn并且这个子序列的长度最长。输出这个最长的长度。•例如：•n=6•482367分析•最长上升子序列问题•设状态：令f[i]代表以i结尾的最长上升子序列长度•分阶段：每个f[i]都是一个阶段•写状态转移方程：•时间复杂度])[][1(1][max][jaiaandijjfif)2^(NO区间动态规划•石子合并•N堆石子排成一列，每一堆有一些石子堆成。每一次合并相邻的两堆，代价为两堆石子的个数。最终要将所有的石子合并为一堆，总的代价就是每一次代价的和。不同的合并方式代价是不同的，所以希望能够得到最小代价。例如：N=57，6，5，7，100贪心思路•每次选择合并代价最小的一组进行合并：•按照贪心法，合并的过程如下：每次合并得分第一次合并7657100=11第二次合并7117100=18第三次合并187100=25第四次合并25100=125•总得分＝11＋18＋25+125＝179••另一种合并方案•每次合并得分第一次合并7657100-13第二次合并1357100-12第三次合并1312100-25第四次合并25100-125•总得分＝13＋12＋25+125＝175分析•设状态：设f[i][j]代表把i~j合并的最小代价•分阶段：按照j-i的值由小到大划分阶段•写状态转移方程：•其中s[i][j]代表从i到j的和•时间复杂度)](][[]][1[]][[min]][[jkijisjkfkifjif)(3NO••