动态规划ppt课件

1、动态规划天津大学1;.2例题：数字方阵n给出一个数字方阵，形式如下：n1 2 3 4n8 7 6 5n9 10 11 12n16 15 14 13n找出从第一层到最后一层的一条路，使得所经过的权值之和最小。要求每一步只能向下，左下和右下这三个方向走。3例题：数字方阵n设f(i, j)是走到第i行第j列时能够得到的最小权值，根据规则最多只有三个格子能走到这个格子：（i-1, j-1），（i-1, j），（i-1, j+1）。要求出到走到位置（i, j）时的能够得到的最小权值，要先求出走到上面那三个位置时的最小权值（为什么？）于是可以列出递归式：nf(i, j) = min f(i-1, j-1)

2、, f(i-1, j), f(i-1, j+1) + wijn然而如果这样直接写成递归程序，效率并不高。4例题：数字方阵n使用二维数组dp，每当算完一个f(i,j)，就把结果保存在dpij中，下次再用到这个结果，可以直接使用，从而避免了重复计算。5动态规划解决的问题n能够用动态规划解决的问题，往往是最优化问题而且问题的最优解的局部往往是局部问题在相应条件下的最优解。而且问题的最优解与其子问题的最优解要有一定的关联，要能建立递推关系，此外，为了体现动态规划的高时效，子问题应当是互相重叠的，即很多不同的问题共享相同的子问题。6动态规划的解题思路n通过划分子问题来缩小问题规模n记录子问题的最优解从而

3、避免重复计算7设计动态规划算法的一般步骤n确定子问题的表示方法（确定状态）n递归地定义最优解的值（状态转移方程）n按自底而上的方式构造最优解的值8动态规划实现的两种方法n自顶而下的记忆化搜索n通过递归的方式，将对问题最优解的求解，归结为求其子问题的最优解，并将计算过的结果记录下来，以后使用时不必重新计算。n自底而上的递推方法9动态规划的分类n编号动态规划n区间动态规划n划分动态规划n数轴动态规划n树形动态规划10编号动态规划一般有两种表示状态的方法：1) 状态i表示前i个元素构成的最优解，可能不包含第i个元素。2) 状态i表示在必须包含第i个元素的情况下前i个元素构成的最优解。11编号动态规划

4、-最长不下降子序列n给定一个序列：a1, a2, , an，从这个序列中选出m个元素：ai1, ai2, , aim，如果i1, i2, , im满足i1 i2 im，那么就把这m个选出的元素组成的序列成为原来序列的子序列。如果子序列满足ai1 ai2 aim，那么就称这个子序列为不下降子序列，这个问题是要求出指定序列的最长不下降子序列。12编号动态规划-最长不下降子序列n分析：假设最长不下降子序列中包含元素ak，那么一定存在一组最优解，它包含了a1, a2, , ak这个序列的最长不下降子序列。n子问题的表示：令dpi表示以第i个元素结尾的前i个元素构成的最长不下降子序列的长度。n递归地定义

5、最优解：ndpi = max dpj | 0 j i; aj ai + 113编号动态规划-最长不下降子序列n伪代码：nFOR i FROM 1 TO nn dpi 0;n FOR j FROM 1 TO i 1n IF aj dpin THEN dpi dpj;n dpi dpi + 1;14编号动态规划-最长不下降子序列n上面的算法的时间复杂度为O(n2)，是否可以优化呢？n分析：设Ai = min aj | dpj = i，那么如果i j，一定可以推出Ai Aj。n状态转移：ndpi = max j | Aj ai + 1; n（maxj | Aj ai可以通过二分查找求出）15编号动态

6、规划-最大局部和n给定一个数列：a1, a2, , an，它的局部和定义为S(i, j) = ai + ai+1 + + aj。求这个数列的最大局部和。16编号动态规划-最大局部和n分析：如果元素ai是最大局部和的一部分，那么只有两种情况：ai是这个局部和的开始元素；或ai接在ai-1之后。n子问题的表示：n令dpi表示以ai结束的最大局部和。n递归地定义最优解：ndpi = maxdpi 1 + ai, ain化简得：dpi = max dpi 1, 0 + ai17编号动态规划-最大局部和n伪代码：ndp0 0;nFOR i FROM 1 TO nn IF dpi 1 0）n最终结果为：maxsumi39树形动态规划-贿赂nA国要申办某项国际会议，它必须争取到m个以上国家的同意才能申办成功。然而，如果不采用贿赂的手段，没有国家会支持A国。在国与国之间存在附庸关系，如果B国是C国的附庸国，那么贿赂了C国就不用再贿赂B国也会获得B国的支持。现在已知n个国家之间的附庸关系，以及贿赂每个国家需要花费的资金，问最少需要花费多少，A国才能申办成功。40树形动态规划-贿赂n国家的关系形成一个森林，用dpij表示在国家i及其子树中，争取到j张选票所需的最