文档介绍：动态规划天津大学例题:数字方阵给出一个数字方阵,形式如下:123487659101**********找出从第一层到最后一层的一条路,使得所经过的权值之和最小。要求每一步只能向下,左下和右下这三个方向走。例题:数字方阵设f(i,j)是走到第i行第j列时能够得到的最小权值,根据规则最多只有三个格子能走到这个格子:(i-1,j-1),(i-1,j),(i-1,j+1)。要求出到走到位置(i,j)时的能够得到的最小权值,要先求出走到上面那三个位置时的最小权值(为什么?)于是可以列出递归式:f(i,j)=min{f(i-1,j-1),f(i-1,j),f(i-1,j+1)}+w[i][j]然而如果这样直接写成递归程序,效率并不高。例题:数字方阵使用二维数组dp[][],每当算完一个f(i,j),就把结果保存在dp[i][j]中,下次再用到这个结果,可以直接使用,从而避免了重复计算。动态规划解决的问题能够用动态规划解决的问题,往往是最优化问题而且问题的最优解的局部往往是局部问题在相应条件下的最优解。而且问题的最优解与其子问题的最优解要有一定的关联,要能建立递推关系,此外,为了体现动态规划的高时效,子问题应当是互相重叠的,即很多不同的问题共享相同的子问题。动态规划的解题思路通过划分子问题来缩小问题规模记录子问题的最优解从而避免重复计算设计动态规划算法的一般步骤确定子问题的表示方法(确定状态)递归地定义最优解的值(状态转移方程)按自底而上的方式构造最优解的值动态规划实现的两种方法自顶而下的记忆化搜索通过递归的方式,将对问题最优解的求解,归结为求其子问题的最优解,并将计算过的结果记录下来,以后使用时不必重新计算。自底而上的递推方法动态规划的分类编号动态规划区间动态规划划分动态规划数轴动态规划树形动态规划编号动态规划一般有两种表示状态的方法:1)状态i表示前i个元素构成的最优解,可能不包含第i个元素。2)状态i表示在必须包含第i个元素的情况下前i个元素构成的最优解。