简单动态规划入门

《简单动态规划入门》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划使用动态规划的条件1、最优子结构2、无后效性最优子结构最短路径：如果某条路径是起点到终点的最短路径，则起点到该路径上的每一点都是最短路径。（最长路径？）无后效性最短路径：当前选择任何一条边都不会影响以后选择其他边。有费用的最短路径：设经过任何一条边时都要耗费一定的费用，总费用一定的情况下，当前选择某一条特定的边可能导致某些其他的边无法被选择。动态规划解题的步骤1、找出最优子结构2、写出动态规划方程3、使用自底向上或者自顶向下的方法求解4、逆推求解动态规划的重点思路与方程程序模型线型动态规划特征：问题的数学模型表现为线型。通常的子结构划分方式：顺序、中分最长递减子序列给定数

2、列a1、a2、…、an，求最长递减子序列。子结构划分：顺序。最优子结构？无后效性？动态规划方程变量的定义：ai::=数列的第i个数fi::=以ai结尾的最长递减子序列长度方程：fi=max{fk}+10<=kaiork=0f0=0Answer=max{fi}1<=i<=n要点小结动态规划方程要点：变量定义，方程递归形式，参数范围，初始条件。程序模型要点：初始条件->变量初始化

3、递归终止条件参数范围->循环变量范围&判断条件方程递归形式->赋值语句矩阵乘法一个a*b的矩阵和一个b*c的矩阵相乘需要a*b*c次乘法，得到一个a*c的矩阵。现在给你一系列矩阵的连乘式，求最少

4、的乘法次数。子结构划分：中分。考虑最后两个矩阵相乘。这两个矩阵必定对应某一个划分，由左右两部分分别计算得到。最优子结构？无后效性？动态规划方程变量的定义：ri::=第i个矩阵的行数ci::=第i个矩阵的列数fij::=将第i-j个矩阵相乘所需的最少乘法次数方程：fij=min{fik+fk+1j}+ri*ck*cji<=k<=jfii=0Answer=f1n取数游戏有n个数a1、a2、…、an。每次从中删去一个数，规定最左最右两个数不能删除。这样共进行n-2次，求得分最高的方案。计分方式：设某一次删除的数为ai，则你的得分为ai-1*ai*ai+1。所有得分相加即为最后总分。动态

5、规划方程变量的定义：fij::=第i-j个数所能得到的最高得分方程：fij=max{fik+fkj}+ai*ak*aj1<=i

6、定义：Vi::=第i件物品的体积Pi::=第i件物品的价值fij::=用容量为j的背包去装前i个物品所能获得的最大总价值方程：fij=max{fi-1j,fi-1j-vi+Pi}f0j=0Answer=fnT环型动态规划特征：问题的数学模型表现为环型。通常思路：转换成线型处理石子合并在一个圆形操场的四周摆放着N堆石子(N<=100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数。记为该次合并的得分。求最小得分。动态规划方程变量的定义：Sij::=第i-j堆石子总数fij::=第i-j堆石子所能得到的最小得分方程：fij=min{fi

7、k+fk+1j}+Sij1<=i<=k<=j<=Nfii=0Answer=f1n平面型动态规划特征：问题模型为一个平面通常的子结构划分方式：逐行扫描迷宫宝藏一个迷宫，入口位于左上角，规定只能往下或者往右走。迷宫中存在一些障碍物无法通过。迷宫的某些地方里藏有不同价值的宝藏。求所能收集的宝藏的最大价值。子结构划分：逐行扫描。考虑迷宫某一点，要求走到这一点所能收集的宝藏的最大价值，先求出走到它左边和上边所能收集的宝藏的最大价值。最优子结构？无后效性？动态规划方程变量的定义：Aij::=迷宫第i行第j列的宝藏价值，-1表示障碍物Sij::=走到第i行第j列所能收集的宝藏的最大价值方程：S

8、ij=max{Sij-1，Si-1j}+AijSij=-1Sij-1=-1andSi-1j=-1ori=0orj=0S11=A11Answer=Smn数字三角一个数字三角形如下所示：3459726874从顶端出发，每次可以向左下或者右下走。求一条从顶端到底边的路径，使得路径上所有数之和最大。字符串匹配给一个带通配符*和?的字符串S，问它能不能匹配字符串T。例如，a*b?能够匹配aabc，但是不能匹配aab思路aabca1100*1111b0010?0001aaba110*111b