动态规划-例题众多-详细讲解选编.ppt

动态规划;F(n) = ;递归 vs 动态规划;方法概要;动态规划算法;最优子结构性质：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。;动态规划;动态规划算法的4个步骤： 1. 刻画最优解的结构特性. （一维，二维，三维数组） 2. 递归的定义最优解. （状态转移方程） 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解. ;实例;例题二. 输入n，求出n！;例题三：排队买票问题;分析：;程序的实现;实例;拓展1： 拦截导弹 （vijos1303）;拓展2：低价购买 ;拓展3：合唱??形 （vijis1098）;例题五. 马拦过河卒;步骤1：用F（X,Y）表示到棋盘上每个阶段(X,Y)的路径条数；;例题六：数字三角形问题;步骤1;拓展：栈（vijos 1122） ; 使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1的过程。（原始状态如上图所示） ;你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。 【输入格式】 输入文件只含一个整数n（1≤n≤18） 【输出格式】 输出文件只有一行，即可能输出序列的总数目 【输入样例】 3 【输出样例】 5;例题七：最长公共子序列;例子;穷举法;给定一个序列Xm = (x1, x2, …, xm),我们定义Xm的第i个前缀为: Xi = ( x1, x2, …, xi ) i = 0, 1, 2, …, m c[i, j]为序列Xi = (x1, x2, …, xi)和Yj = (y1, y2, …, yj)的最长公共子序列的长度. ;状态转移方程;附加信息;LCS-LENGTH(X, Y, m, n) 1 for i ← 1 to m do c[i, 0] ← 0 2 for j ← 0 to n do c[0, j] ← 0 3 for i ← 1 to m do 4 for j ← 1 to n do 5 if xi = yj 6 then c[i, j] ← c[i - 1, j - 1] + 1 7 b[i, j ] ← “↖” 8 else if c[i - 1, j] ≥ c[i, j - 1] 9 then c[i, j] ← c[i - 1, j] 10 b[i, j] ← “↑” 11 else c[i, j] ← c[i, j - 1] 12 b[i, j] ← “←” 13 return c and b;例子;找出最长共同子序列;例题8：0-1背包问题;最优子结构;0-1背包问题的动态规划;Knapsack (S,W) 1 for w ← 0 to w1 - 1 do P[1, w] ← 0; 2 for w ← w1 to W do P[1, w] ← v1; 3 for i ← 2 to n do 4 for w ← 0 to W do 5 if wi w then 6 P[i,w] ← P[i-1, w]; 7 else 8 P[i,w] ← max{P[i-1, w], P[i-1,w-wi] + vi};0-1背包问题的动态规划;P(i, w) = max {vi + P(i - 1, w-wi), P(i - 1, w) } ;构造最优解法;子问题的重复;子问题的重复;拓展1：装箱问题 （vijos 1133）;拓展2：采药 (vijos1104);拓展3：开心的金明 （vijos 1317）;输出格式 Output Format ;拓展4：金明的预算方案 (vijos 1313 );输入格式 Input Format ;例题9：石子归并;输入:44?5??9??4?输出:－４??５??９?－４－８?－５?９－１３??－９２２ ４??－５??－９??４４??－１４??－４－４??－１８２２;用〔i，j〕表示一个从第i堆数起，顺时针数j堆时的子序列｛第i堆、第i