Pascal动态规划 .pptVIP

动态规划---入门篇 Dynamic programming 多阶段决策过程 多阶段决策过程（ multistep decision process ）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。 动态规划（dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。 求解问题的两个重要性质 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（ 即满足最优化原理 ）。最优子结构性质为动态规划算法解决问题提供了重要线索。 子问题重叠性质：在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。 动态规划与分治、递归、贪心的区别 递归算法在程序实现上直观容易，但因为子问题被重复计算，且程序背后存在对栈的操作，速度（计算复杂度一般是指数级的）上劣于动态规划。在递归的过程中，通过保存子问题的结果，可以减少计算量，同样是空间换时间的思想，称作memoization算法。 分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。这就是动态规划高效的一个原因。 在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。 最短路径问题 图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? [题1] 最长不下降子序列 【问题描述】 设有整数序列b1,b2,b3,…,bm，若存在i1i2i3…in，且bi1bi2bi3…bin，则称 b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列 输入：整数序列 输出：最大长度n [题1] 最长不下降子序列 【分析】 设F(i)为前I个数中的最大不下降序列长度。由题意不难得知，要求F(i)，需要求得F(1)—F(i-1)，然后选择一个最大的F(j) ( ji, bibj )，那么前I个数中最大不下降序列便是前j个数中最大不下降序列后添加bi而得。可见此任务满足最优子结构，可以用动态规划解决。 通过上面的分析可得状态转移方程如下： F(i)=max{F(j)+1} (ji, bjbi) 边界为F(1)=1 【部分代码】 f[1]:=1;len:=1; {求解最大不下降序列长度} for i:=2 to n do begin f[i]:=1; for j:=1 to i-1 do if (b[i]b[j])and(f[i]f[j]+1) then f[i]:=f[j]+1; if f[i]len then len:=f[i] {记录最大值} [题2] 数塔 如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最大。数塔层数用n表示，1=n=100。 [题2] 数塔 贪心法。时间上有保证，但得不到最优解。主要原因是贪心法只顾眼前利益，不考虑长远利益。 在规定时间内得到正确结果，唯一的方法就是“动态规划”。 下面以示意图表示动态规划的过程：所选路径为：9-12-10-18-10 注意分析时，有以下几个特点： （1）将问题划分成了4个阶段； （2）每个阶段均得到了“部分”的最优解，得到最优解时，需要进行条件判断； （3）从最下面一层往顶层推导。 [题3] 棋盘路径问题 【题目简介】 有一个n*m的棋盘，左下角为（1,1），右上角为（n,m），如下图：? 有一颗棋子，初始位置在（1,1），该棋子只能向右走或者向上走，问该棋子从（1,1）到（n,m）一共有几条路径？ 输入：两个整数n和m 输出