动态规划及其应用(一)

《动态规划及其应用(一)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划及其应用（一）清华大学杨志灿动态规划术语阶段把所求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解状态状态表示每个阶段开始面临的自然状况或客观条件决策（转移）一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。边界转移过程中的初始情况策略由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。动态规划DynamicProgramm

2、ing求解决策过程最优化的数学方法适用条件最优化原理（最优子结构性质）无后效性子问题的重叠性范围因同样有状态、转移方程、无后效性等性质，故将递推等类型也纳入DP之下如计算方案数、期望值数字三角形给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。输入数据的第1行是数字三角形的行数n，1<=n<=100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。5738810274445265IOI1994数字

3、三角形用a[i][j]表示第i行第j个数字的大小转移方程用f[i][j]表示从（1，1）到（i，j）的最优路径的数字和f[i][j]=max{f[i-1][j-1],f[i-1][j]}+a[i][j];“顺推”式更新f[i][j]+a[i+1][j]f[i+1][j]f[i][j]+a[i+1][j+1]f[i+1][j+1]时间复杂度O（n^2）数字三角形7i=138i=2810i=3阶段2744i=445265i=5状态f[i][j]决策（转移方程）f[i][j]=ma

4、x{f[i-1][j-1],f[i-1][j]}+a[i][j];策略FOR(i,1,n)FOR(j,1,i)转移方程路径个数给定一n*m网格，求从左上角到右下角的路径总数只允许向下或向右走路径个数动态规划f[i][j]表示从左上角到（i,j）的方案数转移方程f[i][j]=f[i-1][j]+f[i][j-1]边界：f[i][0]=0；f[0][j]=0；时间复杂度O（nm）直接计算C（n+m,n）时间复杂度O（(n+m)*运算）运算=高精度/模运算求逆元路径个数给定一n*

5、m网格，求从左上角到右下角的路径总数只允许向下或向右走某些格子不允许经过路径个数动态规划f[i][j]表示从左上角到（i,j）的方案数转移方程if(pass[i][j])f[i][j]=f[i-1][j]+f[i][j-1]；elsef[i][j]=0；时间复杂度O（nm）路径个数状态f[i][j]阶段路径个数给定一n*m网格，求从左上角到右下角的路径总数只允许向下或向右走某些格子不允许经过至多改变p次方向无后效性如何设计状态怎样的状态能完整记录需要的信息路径个数状态

6、f[i][j][k][2]表示从左上角到（i,j）已改变了k次方向且最后一步的方向为0或1的方案数转移方程根据状态列写时间复杂度O（nmp）路径个数给定一n*m网格，求从左上角到右下角的路径总数只允许向下或向右走某些格子不允许经过练练看改变方向次数在[L,R]内不允许连续改变方向t步之内必须转向对于任一格点（x，y），（x，y）和（x+1，y+3）不能都在路径上路径个数给定一n*m网格，格点有正整数权值，求从左上角到右下角的最优路径最优路径为权值总和最大的路径只允许向下或向右走

7、某些格子不允许经过路径个数状态最优子问题性质f[i][j]表示从左上角到（i,j）的最优路径的值转移方程f[i][j]=max{f[i-1][j],f[i][j-1]}+a[i][j]时间复杂度O（nm）路径个数给定一n*m网格，格点有正整数权值，求从左上角到右下角的最优路径最优路径为权值总和对p取模最大的路径只允许向下或向右走某些格子不允许经过状态设计最优子问题性质仍使用f[i][j]可以吗？路径个数状态最优子问题性质f[i][j][k]表示是否存在一条从左上角到（i,

8、j）的路径，路径和对p取模为k转移方程略时间复杂度O（nmp）路径个数给定一n*m网格，格点有正整数权值，求从左上角到右下角的最优路径只允许向下或向右走某些格子不允许经过练练看最优路径为平均数最小的路径最优路径为权值最大值与最小值之差最小的路径最优路径为路径上相邻格点的差的最大值最小的路径最优路径为路径上任意5个相邻的格点的和的最大值最小的路径背包问题给定若干种物品，每种物品都有自己的重