动态规划设计-例题众多-详细讲解.ppt

动态规划 斐波纳契数列F(n) 递归 vs 动态规划 方法概要 构造一个公式，它表示一个问题的解是与它的子问题的 解相关的公式.E.g. F(n) = F(n-1) + F(n-2). 为这些子问题做索引 ，以便它们能够在表中更好的存储与检索 (i.e., 数组array【】) 以自底向上的方法来填写这表格; 首先填写最小子问题的解. 这就保证了当我们解决一个特殊的子问题时, 可以利用比它更小的所有可利用的 子问题的解. 动态规划算法 算法思想 将待求解的问题分解成若干个子问题，并存储子问题的解而避免计算重复的子问题，并由子问题的解得到原问题的解。 动态规划算法通常用于求解具有某种最优性质的问题。 动态规划算法的基本要素： 最优子结构性质和重叠子问题。 最优子结构性质：问题的最优解包含着它的子问题的最优解。即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。 重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。对每个子问题只解一次，然后将其解保存起来，以后再遇到同样的问题时就可以直接引用，不必重新求解。 动态规划 动态规划算法的4个步骤： 1. 刻画最优解的结构特性. （一维，二维，三维数组） 2. 递归的定义最优解. （状态转移方程） 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解. 例题一. 斐波纳契数列F(n) 例题二. 输入n，求出n！ 例题三：排队买票问题 一场演唱会即将举行。现有n个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti（1≤i≤n），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，假如RjTj+Tj+1，这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程。现给出n, Tj和Rj，求使每个人都买到票的最短时间和方法。 程序的实现 BuyTicks(T, R) 1 n ← length[T] 2 f[0] ← 0 3 f[1] ← T[1] 4 for i ← 2 to n do 5 f[i] ← f[i-2]+R[i-1] 6 if f[i] f[i-1]+T[i] then 7 f[i] ← f[i-1]+T[i] 8 return f 例题四：求最长不降子序列 例题五. 马拦过河卒 例题七：最长公共子序列 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 最长公共子序列:公共子序列中长度最长的子序列。 最长公共子序列问题 给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。 例如: X = (A, B, C, B, D, A, B) X的子序列: 所有X的子集(集合中元素按原来在X中的顺序排列) (A, B, D), (B, C, D, B), 等等. 例子 X = (A, B, C, B, D, A, B) X = (A, B, C, B, D, A, B) Y = (B, D, C, A, B, A) Y = (B, D, C, A, B, A) (B, C, B, A)和(B, D, A, B)都是X和Y 的最长公共子序列(长度为4) 但是,(B, C, A)就不是X和Y的最长公共子序列 穷举法 对于每一个Xm的子序列,验证它是否是Yn的子序列. Xm有2m个子序列 每个子序列需要o(n)的时间来验证它是否是Yn的子序列. 从Yn的第一个字母开始扫描下去,如果不是则从第二个开始 运行时间: o(n2m) 给定一个序列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