• 1. 动态规划不要重复你的计算
  • 2. 问题:数塔问题有形如右图的一个数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的数值和最大。 9121510682189519710416
  • 3. 数据存储912151068218951971041690000121500010680021895019710416所有的节点存在一个二维数组的下三角中第(i,j)节点的左右分支分别存放在(i+1,j)和(i+1,j+1)中(i,j)(i+1,j+1)(i+1,j)
  • 4. 求解暴力求解,列举出所有可能的路径,并计算这些路径上数字的和。如何保存这些路径呢?每一步保存一个数据,向左是0,向右是1,然后形成一个个数和树高一样的0、1字符串,把这个字符串转化为10进制,作为数组下标912151068218951971041601106a[6] = 9+12+6+9+10 = 46 选出数组中最大的元素,再把数组元素下标从十进制转化为2进制就可以得到我们要求的路径了
  • 5. 观察考虑我们曾经讲过的分治思想9121510682189519710416121062189197104156818957104169整体的最长距离相当于左右两颗子树的最长距离加上9,左右子树的最优解可以如此分解下去最优子结构
  • 6. 求解90000121500010680021895019710416分治策略通常使用递归#define N 5 int a[N][N]; int max(int i, int j, int n) { int left,right; if ((i==n)||(j==n)) return a[i][j]; left=max(i+1,j,n); right=max(i+1,j+1,n); return (left>right)? (left+a[i][j]) : (right+a[i][j]); }   int main() { int maxlength; maxlength = max(0, 0, N-1); return 0; }max(1,1,n)max(2,1,n)max(2,2,n)max(3,1,n)max(3,2,n)max(3,3,n)
  • 7. 看看能不能优化121062189197104156818957104169以6为根的这棵树的最长路径会被重复计算两次,因为他分别是12的右子树和15的左子树187109104重复计算3次当树的高度增加时,出现重复计算的情况就会非常明显,从第三层开始(计算两次),到倒数第二层都会有重复计算的子树出现,而且越到下面重复计算的次数越多重叠子问题
  • 8. 如何减少重复呢?自顶向下记录法 自底向上方法
  • 9. max(4,1,n)max(4,2,n)max(4,3,n)自顶向下记录法依然采用自顶向下的递归方法,但是每次计算一个和节点相关的最大长度,就把这个长度和节点编号一起记录下来,以后再需要此节点的最大长度就不在计算,而是直接是用,此方法的过程相当于对树进行深度遍历的过程max(1,1,n)max(2,1,n)max(2,2,n)max(3,1,n)max(3,2,n)max(3,3,n)max(4,4,n)max(5,1,n)max(5,2,n)max(5,3,n)max(5,4,n)max(5,5,n)m[4][1] = 21m[4][2] = 28m[3][1] = 38m[4][3] = 19m[3][2] = 34m[2][1] = 50m[4][4] = 21m[3][3] = 29m[2][2] = 49m[1][1] = 59
  • 10. 程序实现#define N 5 int a[N][N]; int data[N][N];   int max(int i, int j, int n) { int left,right; if ((i==n)||(j==n)) { data[i][j] = a[i][j]; return a[i][j]; }else if(data[i][j] != 0 ) { return data[i][j]; } left=max(i+1,j,n); right=max(i+1,j+1,n); data[i][j] = (left>right)? (left+a[i][j]) : (right+a[i][j]); return data[i][j]; }#define N 5 int a[N][N]; int max(int i, int j, int n) { int left,right; if ((i==n)||(j==n)) return a[i][j]; left=max(i+1,j,n); right=max(i+1,j+1,n); return (left>right)? (left+a[i][j]) : (right+a[i][j]); }   int main() { int maxlength; maxlength = max(0, 0, N-1); return 0; }
  • 11. 如何得到选择的路径呢9000012150001068002189501971041659000050490003834290021281921019710416adata第(i,j)节点的左右分支分别存放在(i+1,j)和(i+1,j+1)中左左右右
  • 12. 自底向上方法9 (59)12 (50)15 (49)10 (38)6 (34)8 (29)2 (21)18 (28)9 (19)5 (21)19710416上层的计算依赖下层的计算,采用与递归方法方向相反的方法
  • 13. 程序实现#define N 5 int a[N][N]; int data[N][N]; int dir[N][N];   int main() { int left,right; for(int i=N-1; i>=0; i--) { for(int j=0; j<=i; j++) { if(i == N-1) { data[i][j] == a[i][j]; }else{ left = data[i+1][j]; right = data[i+1][j+1]; if (left > right) { data[i][j] = left + a[i][j]; dir[i][j] = 0; }else{ data[i][j] = right + a[i][j]; dir[i][j] = 1; } } } } }90000121500010680021895019710416590000504900038342900212819210197104160000000000101000101000000adatadir
  • 14. 在编程中要注意的硬盘总比内存便宜很多内存总比时间便宜很多用空间换取时间
  • 15. 与分治算法有什么异同?
  • 16. 两种算法的异同分治算法动态规划如何求出问题的解如何求出问题的最优解自底向上简单递归递归记录法可以分解为彼此不重叠的子问题每个子问题可以用和父问题相同的方法求解父问题的最优解包含子问题的最优解子问题并不总是全新的问题,而是存在重叠最优子结构重叠子问题观察发现在使用普通循环和递归式出现的重复计算问题归纳总结出问题的最优解和子问题的最优解之间的关系发现动态规划方法可以减少计算找到如何用动态规划求解的方法
  • 17. 动态规划基本步骤找出最优解的性质,并刻划其结构特征。递归地定义最优值以自底向上的方式计算出最优解的值,并在这个过程中记录最优解以递归记录法计算出问题的最优解的值根据最优解得值构造最优解
  • 18. 基本概念,另一个角度9121510682189519710416阶段1阶段2阶段3阶段4阶段5决策决策决策决策状态阶段:把问题分成几个相互联系的有顺序的几个环节,这些环节即称为阶段状态:某一阶段的出发位置称为状态。通俗地说状态是对问题在某一时刻的进展情况的数学描述决策:从某阶段的一个状态演变到下一个阶段某状态的选择状态转移方程:根据上一阶段的状态和决策导出本阶段的状态。这就像是“递推”多阶段决策问题
  • 19. 从最优解得角度来说,找到最优子结构是求解的关键从多阶段决策角度来说,找到状态转移方程式求解的关键
  • 20. Problem:滑雪问题全国青少年信息学奥林匹克竞赛上海市队选拔赛 2002 http://poj.org/problem?id=1088
  • 21. 题目描述12345161718196152425207142322218131211109Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子。 一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。 Input:输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。Output输出最长区域的长度。
  • 22. 分析与求解数组m[N][N]保存着每个点的高度数组a[N][N]代表以每个点位起点的最长线路的长度a[i][j]的值是,周围四个点中高度比m[i][j]的那些点中,以自身为起点的最长线路长度+1(i,j+1)(i-1,j)(i,j-1)(i,j)(i+1,j)1243if (m[i-1][j] < m[i][j] ) return a[i-1][j]+1; else return 0if (m[i+1][j] < m[i][j] ) return a[i+1][j]+1; else return 0if (m[i][j-1] < m[i][j] ) return a[i][j-1]+1; else return 0if (m[i][j+1] < m[i][j] ) return a[i][j+1]+1; else return 0a(i,j) max=
  • 23. 解结构分析(i,j+1)(i-1,j)(i,j-1)(i+1,j)(i-1,j+2)(i+1,j+2)(i,j)(i,j+3)(i,j+2)重叠子问题用自顶向下递归记录法:每次计算了一个新的点的最大高度值就将其记录下来
  • 24. 求解过程—自底向上我们发现计算任何一个点的最长距离,所需要的子问题的信息都是他周围高度比他低的点的最大长度如果可以根据矩阵内点的从小到大的顺序计算每个点最长距离这样当需要计算某个点的最长距离是,需要的周围的点的最长距离都已经知道了,可以避免重复计算用三个数n*n的一维数组,分别存放矩阵中的点的高度值,点坐在的x坐标与y坐标,对高度值所在的数组进行排序,并根据排序的移动相应的移动对应的x坐标与y坐标的数组v1234516171819x111112222y12345123412345161718196152425207142322218131211109
  • 25. Problem:矩阵连乘经典问题
  • 26. 矩阵相乘基本知识M*N与N*P的矩阵相乘需要的计算量是M*N*P#define M 100 #define N 200 #dfeine P 50   float a[M][N]; float b[N][P]; float c[M][P];   for(int i=0; i
  • 27. 矩阵连乘给定n个要相乘的矩阵构成的序列A1,A2,…,An,Ai与Ai+1是可乘的,要计算乘积 A1A2…An 但是由于矩阵乘法具有结合律,所以可以有很多种计算顺序,我们给矩阵相乘加上括号来表示他们相乘的顺序 一个矩阵的乘法是加全部括号的 如果他是单个矩阵 两个加全部括号的矩阵的乘积外再加括号
  • 28. 举例A1,A2, A3,A4 四个矩阵相乘可能的顺序不同顺序的三个矩阵相乘所需运算量不同 A1 10x100 A2 100X5 A3 5X50(A1 ( A2 (A3A4)))(A1 (( A2 A3)A4))((A1A2)( A3A4))((A1(A2 A3)) A4)(((A1A2) A3) A4)((A1A2) A3) 10*100*5 +10*5*50 =7500 (A1(A2 A3)) 100*5*50 +10*100*50 =75000
  • 29. 问题描述给定n个矩阵构成一个链< A1,A2,…,An >,矩阵Ai的维数为pi-1 x pi,i=1,2,3…..n;对乘积A1A2…An以一种最小化乘法次数的方式进行加全部括号,也就是确定这个序列相乘的顺序A1A2A3Ai-1AiAi+1An…..…..p0xp1p1xp2p2xp3pi-2xpi-1pi-1xpipixpi+1Pn-1xpn用p0 p1 p2…..pn这n+1个数来表示可连乘的n个矩阵的大小
  • 30. 穷举法如何例举出所有的求解次序每次都是两个矩阵相乘,最后一步也是两个矩阵相乘,最后一步只有n-1种可能(A1 ( A2 (A3A4)))(A1 (( A2 A3)A4))( (A1A2) ( A3A4) )((A1(A2 A3)) A4)(((A1A2) A3) A4)12341123421234312341234123412341234234234123123
  • 31. 穷举法的时间复杂度用P(n)表示n个矩阵可能的所有加全括号方案数 n=1时,P(n)=1 n>=2时,就是两个加全部括号的子序列的乘积的乘积,分裂发生在第k处时,方案数为P(k)P(n-k)Ω(4n/n3/2)
  • 32. 分析问题的最优子结构1我们记m[i,j]代表对矩阵连乘AiAi+1…Aj求得的最少计算量,其中i<=j 最少计算量乘积的最后一步肯定是两个矩阵B、C相乘,我们假设这两个矩阵分别为: B:第i到k的矩阵的乘积 C:第k+1到j的矩阵的乘积, S=AiAi+1…AkAk+1…AjB = AiAi+1…AkC = Ak+1…Aj等价于:假设最后一步在k处分可以得到最少的计算量
  • 33. 分析问题的最优子结构2S = AiAi+1…AkAk+1…AjB = AiAi+1…AkC = Ak+1…Ajm[i,j]m[i,k]m[k+1,j]m[i,j] = m[i,k] + m[k+1,j] + pi-1 x pk x pjpi-1 x pjpi-1 x pkpk x pj为什么整体的最优解一定要求子问题的最优解呢?
  • 34. 分析问题的最优子结构3我们前面假设得到最优解得最后一步出现在划分k处,实际上我们不知道这个k到底是多少,但是我们知道这个k可以达到计算量最小 当只剩一个矩阵时,已经不需要计算了,所以有 m[i,i] = 0 , 1<=i<=jm[i,j] = min( m[i,k] + m[k+1,j] + pi-1 x pk x pj ), i<=k
  • 35. 求解过程我们可以从m[i,i] (i=0,1,…,n-1)开始,逐步推算m[i,i+1] (i=0,1,…n-2),m[I,i+2] (i=0,1,…n-3)…….,我们最终的目标是计算m[0,n-1] 用一个n+1个元素的数组p存放数组维数 用一个n*n的二位数组m来存放m的值 用附加的一个n*n的数组s来存放每次取最小值的时候所决定的k,也就是可以达到最小值的分隔点,我们将通过这个矩二维数组构造一个最优解
  • 36. #define N 6 int p[N]; int m[N][N]; int s[N][N];   for(int i=0; i
  • 37. 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  • 38. 例子m[2][5]123456101575078752026254375307502500401000350050500060矩阵规模A13035A23515A3155A4510A51020A62025
  • 39. 构造最优解123456101133320233330333404550565123456101133320233330333404550565((A1A2A3)(A4A5A6))((A1 ( A2A3)) (A4A5)A6))从3处将1-6分为1-3和4-6两段,查看s[1][3]和s[4][6]将1-3从1处分为1和2-3 将4-6从5处分为4-5和6
  • 40. 通过以上这个问题,我们已经基本了解了动态规划的整体框架以及实现步骤,在之后的问题中,我们只考虑如何找到并正确的写出最优子结构以及发现重叠子问题,而不再对整个过程加以阐述
  • 41. Problem:最长公共子序列 (LCS)经典问题
  • 42. 子序列若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。 BCBDABACDBB23456712341严格递增下标序列{2,3,5,7}
  • 43. 问题描述给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},找出X和Y的最长公共子序列(LCS)
  • 44. 最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ,则 (1)若xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列。 (2)若xm≠yn且zk≠xm,则Z是Xm-1和Y的最长公共子序列。 (3)若xm≠yn且zk≠yn,则Z是X和Yn-1的最长公共子序列。 具体证明见《算法导论》P209 定理15.11234都是用反证法来证明
  • 45. 反证法与数学归纳法有50位猎人每人养了一条狗,这些狗中至少有一条病狗,这些猎人要找出病狗,并由自己的主人把它枪杀了,第一天,没有听到枪声,第二天也没有听到,第三天听到一片枪声,问有多少只病狗?
  • 46. 算法运行过程要寻找X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列比较 xm和yn如果xm=yn,寻找X={x1,x2,…,xm-1}和Y={y1,y2,…,yn-1}的最长公共子序列,并加上xm如果xm≠yn,选择下面两个公共子序列中较长的那个寻找X={x1,x2,…,xm-1}和Y={y1,y2,…,yn}的最长公共子序列寻找X={x1,x2,…,xm}和Y={y1,y2,…,yn-1}的最长公共子序列如果我们记C[i, j]是X={x1,x2,…,xi}和Y={y1,y2,…,yj}的最长公共子序列C[m,n]C[m-1,n-1]C[m-1,n]C[m,n-1]
  • 47. 最优子结构如何用递归记忆法和自底向上法求解能,如何记录到底哪些元素师两个序列的公共子序列呢?作业:参考《算法导论》15.4节用两种方法实现
  • 48. Problem:最长递增子序列 (LIS)经典问题
  • 49. 问题描述给定一个整数序列,可以从中抽取出一个子序列,使得这个子序列中的元素是递增的,请写出一个时间复杂度尽量低的程序找到这个序列的最长的递增子序列1-12-34-56-71246-1246
  • 50. 解法1:利用LCS1-1234-56-7我们将原序列排序-7-5-3-11246原序列求这两个序列的LCS1-1234-56-7-75-3-112461-1234-56-7-75-3-112461246-1246
  • 51. 解法2:动态规划我们令f[i]代表前i个中最长的递增子序列的长度那么f[i+1]如何表示呢,也就是增加了一个元素array[i]之后能否和之前的子问题f(k)(1<=k<=i)建立起关系呢?关键问题是新增的这个元素array[i],与构成f(k)的那个序列的最后一个元素是什么关系?如果array[i]大于那个元素,就可以构成一个新的递增序列,但是我们没有记录这些信息。即使记录了,要写出这个式子也会很烦。我们令f[i]代表以array[i]结尾的最长递增子序列的长度f[i+1]如果array[i+1]是array[1]….array[i+1]中最小的那个,那么f[i+1] = 1如果array[i+1]不是array[1]….array[i+1]中最小的那个,那么我们肯定对于那些array[k] < array[i+1] 的k,可以把array[i+1]放到那些原来以array[k]结尾的序列后面,形成新的序列,f[i+1]应该是这些序列的长度最长的f[i+1] = max{ 1, f[k]+1} 其中k<=i,且array[k] < array[i+1]我们用自底向上的方法很容易求解f[1]……f[N]我们在求出f[1]……f[N]的最大值,这个最大值就是问题的解1-1234-56-711-11-121-121-1231-123
  • 52. 计算复杂度参考: 《编程之美》2.16题的解法二和解法三 http://www.felix021.com/blog/read.php?1587 #define MAX 1000   int main() { int array[MAX]; int lis[MAX]; for(int i =0; i< MAX; i++ ) { lis[i] = 1; for(int j=0; j array[j] && lis[j]+1 > lis[i]) { lis[i] = lis[j] + 1; } } } return max(lis); }我们通过添加一个数组B,B[j]表示长度为j的所有递增序列中最大值最小的那个数,可以将问题的时间复杂度降为O(nlgn)时间复杂度O(n2)
  • 53. Problem:数组最大子段和经典问题 微软亚洲研究院2006年笔试题20%
  • 54. 题目描述一个有N个元素的数组A[0:N-1],那么连续子数组之和的最大值是多少?{1, -2, 3, 5, -3, 2}{0, -2, 3, 5, -1, 2}{-9, -2, -3, -5, -3}89-2
  • 55. 暴力求解分别求出sum[i:j]的和,并求最大值#define N 1000   int main() { int a[N]; int maximum = a[0]; int sum; for(int i=0; i maximum) { maximum = sum; } } } }sum[i:j]的和等于sum[i:j-1]+a[j]#define N 1000   int main() { int a[N]; int maximum = a[0]; int sum; for(int i=0; i maximum) { maximum = sum; } } } } O(N3)O(N2)
  • 56. 分治策略A[1:n]的最大子段和A[1:n/2]的最大子段和A[n/2+1:n]的最大子段和A[i:n/2]和最大值A[n/2+1:j]的最大值A[n/2+1:n/2+1]A[n/2+1:n/2+2]A[n/2+1:n/2+3]A[n/2+1:j]A[n/2:n/2]A[n/2-1:n/2]A[n/2-2:n/2]A[i:n/2]….….….….MAXMAX++时间复杂度O(n)T(n)= 2T(n/2)+O(n) T(n) = O(nlgn)
  • 57. 能否进步一优化呢假设最大的一段子数组为A[i]……A[j],他与A[0]之的关系0=i=j时,A[i]本身构成最大一段数组0=i
  • 58. #define N 1000   int main() { int A[N], Start[N], All[N]; //initialize A Start[N-1] = A[N-1]; All[N-1] = A[N-1]; for(int i=n-2; i>=0; i--) { Start[i] = max(A[i],A[i]+Start[i+1]); All[i] = max(Start[i],All[i+1]); } //All[0] is the maxsum return 0; }All[p-1] = max{A[p-1], A[p-1]+Start[p], All[p]}Start[p-1] = max{A[p-1], A[p-1]+Start[p]}时间复杂度O(N)
  • 59. 扩展问题如果不是一个数组,而是一个环,也就是一个首尾相连的数组,求他的最大子段和,情况会是怎么样呢? 如果不是一维数组而是二维数组,情况又会如何呢?参考: 《编程之美》2.14题与2.15题
  • 60. Problem:棋盘分割问题全国青少年信息学奥林匹克竞赛1999年 第二天 问题1 Chess
  • 61. 题目描述将一个8X8的棋盘进行分割,每次割下一块矩形的棋盘并使剩下的棋盘也是矩形,再将剩下的继续分割,这样分割了n-1次之后,连同最后剩下的矩阵棋盘共有n块矩形棋盘。
  • 62. 原棋盘上每一格有一个分值,一块矩形棋盘的总分值为其所含各格的分值之和,现在需要将棋盘按上述规则分割成n块,并使各矩形棋盘的总分的均方差最小
  • 63. 分析问题相当于求每个棋盘的总分的平方和最小(x1,y1)(x2,y2)设左上角坐标为(x1,y1)右下角坐标为(x2,y2)的棋盘的总分值的平方为s[x1,y1,x2,y2],切割k次之后得到的k+1块棋盘的总平方和最小为d[k,x1,y1,x2,y2]我们最后要求的是d[n,0,0,8,8]
  • 64. s[x1,y1,a,y2](x1,y1)(x2,y2)x=a(x1,y1)(x2,y2)x=a(a,y2)(a,y1)d[k-1,a,y1,x2,y2]d[k-1,x1,y1,a,y2](x1,y1)(x2,y2)x=a(a,y2)(a,y1)s[a,y1,x2,y2]d[k,x1,y1,x2,y2]= min { min{s[x1,y1,a,y2]+d[k-1,a,y1,x2,y2], s[a,y1,x2,y2]+d[k-1,x1,y1,a,y2]} x1
  • 65. Problem:编辑距离腾讯2007年校园招聘面试题
  • 66. 问题的实际意义 系统是如何知道的?问题描述:给出一个词典,词典中没有的单词被认为是错误的单词,根据词典中的单词对用户输入的错误单词进行纠错
  • 67. 问题转化ocurranceoccurrence在字典中找到与输入单词最“相近”的单词如何定义两个字符串的相似度呢?生物学中,有机体的基因组被划分为巨大的成为染色体的线状DNA分子,基因可以表示成包含了A、C、G、T的一个串。那如何通过判断两个病毒的基因是否相似来判断是否能使用同一种药物呢?
  • 68. 编辑距离俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名,称为Levenshtein distance,也叫做Edit distance两个字符串s1,s2的编辑距离是指,把s1和s2变成相同字符串(或者将一个字符串变为另一个字符串)需要下面操作的最小次数1.把某个字符ch1变成ch2 2. 删除某个字符 3.插入某个字符ocurranceoccurrences1s2dis(s1,s2) = 2
  • 69. 计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质: s1s2考虑最优子结构d(s1,””) = d(“”,s1) = |s1|d(ch1,ch2) = ch1 == ch2 ? 0 : 1;d(s1+ch1, s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 , d(s1+ch1,s2)+1, d(s1,s2+ch2)+1 ); 假设求两个字符串x[1:M], y[1:N]的编辑距离 我们记dis(i,j)为x[1:i]和y[1:j]的编辑距离dis(i,0) = i, dis(0,i) = idis(1,1) = x[i]==y[1]?0:1dis(i+1,j+1) = min { dis(i,j)+x[i+1]==y[j+1]?0:1, dis(i+1,j)+1, dis(i,j+1)+1 }最终要计算dis[M,N]
  • 70. POLYNOMIAL0E1XPOBENTIAL6假设求两个字符串x[1:M], y[1:N]的编辑距离 我们记dis(i,j)为x[1:i]和y[1:j]的编辑距离dis(i,0) = I, dis(0,i) = dis(1,1) = x[i]==y[1]?0:1dis(i+1,j+1) = min { dis(i,j)+x[i+1]==y[j+1]?0:1, dis(i+1,j)+1, dis(i,j+1)+1 }最终要计算dis[M,N]EXPONENTIALPOLYNOMIALii+1jj+1123456789101234567891011自底向上
  • 71. 更近一步考虑编辑距离的缺陷 用户输入bsg是和bug更相似还是与bag更相似呢 是否替换、插入、删除有着不同的概率呢?
  • 72. 回到最初的问题既然已经知道如何定义两个字符串的相似度了,那么如何进行纠错呢。难道需要遍历词典中的所有词条么。45万又让我想起了百度的一道面试题给定一个词典,词典中有很多的单词,现给出一篇英文文章,问词典中的单词一共在文章中出现了多少次?
  • 73. 还是把问题转化一下字典中是按什么方式存储这些单词的呢?
  • 74. TRIE树(Retrieval)假设有b,abc,abd,bcd,abcd,efg,hii这六个单词一棵26叉树说明到此为止的路径构成一个单词
  • 75. 还是回到纠错的问题要找和用户输入相近的,也就是两者编辑距离较小的 例如dis(error,correct) <= MDdis(error,correct) >= abs(length(error) – length(correct))所以我们将字典中具有相同长度的字符串分为一组,每组的代号就是这组中单词的长度,得到K个组length(error)-MD <= length(correct) <= length(error)+MD通常MD为1或者2更好的选择是错误单词长度的四分之一MD>=abs(length(error) – length(correct))K2MD
  • 76. 编辑距离性质编辑距离的性质:令d(x,y)表示字符串x到y的编辑距离,那么显然 d(x,y) = 0 当且仅当 x=y  (编辑距离为0 <==> 字符串相等) d(x,y) = d(y,x)     (从x变到y的最少步数就是从y变到x的最少步数) d(x,y) + d(y,z) >= d(x,z)  (从x变到z所需的步数不会超过x先变成y再变成z的步数) 那是不是在这2MD个组中的每个都要检查呢?
  • 77. 进一步考虑如果dis(error, y) = 1 MD+1,即y和z有至少MD+2个字符不一样dis(y, z) <= dis(z,error) + dis(error,y) = dis(error,z) + dis(error,y) dis(error,z) >= dis(y,z)-dis(error,y) > MD+1 – 1 = MDz不需要检查怎么知道哪些该检查哪些不该呢1973年,Burkhard和Keller提出的BK Tree方法推荐阅读 http://www.matrix67.com/blog/archives/333 http://hi.baidu.com/daizongh/blog/item/669d631636e6bc4e21a4e954.html
  • 78. Problem:01背包问题经典问题
  • 79. 问题描述你去一个岛上寻宝,发现了一个宝藏,其中有n块重量不同的金砖,我们给这n块金砖进行编号1,2,….,n,他们的重量分别为w1,w2,……,wn。我们希望拿走的金装的总重量尽量重。但是背包最多只能承重W重量。请问如何选择。简单起见:假设所有数值都是正整数
  • 80. 问题转化我们可以将问题改写成
  • 81. 如果让你手动去选该怎样呢?
  • 82. 大问题的最优解和子问题最优解如果我们用m(k,j)代表如下子问题即m(k,j)是背包容量为j,可选择物品为1,2,…,k时问题的最优值
  • 83. 问题描述你去一个岛上寻宝,发现了一个宝藏,其中有n块重量不同的宝贝,我们给这n块金砖进行编号1,2,….,n,他们的重量分别为w1,w2,……,wn;他们的价值分别为v1,v2,….,vn。我们希望可以拿走的宝贝的总价值尽力那高。但是背包最多只能承重W重量。请问如何选择。
  • 84. Problem:方块消除IOI( International Olympiad in Informatics )2003 中国国家集训队讨论题 http://poj.org/problem?id=1390统计单词个数
  • 85. 问题描述N个带颜色的方块排成一列,相同颜色的方块连成一个区域,游戏时你可以选择任意一个区域消除,设这个区域包含的方块数是x,则将得x2到个分值,方块消去之后其右边的所有方块就会向左移动,与被消去的方块区域的左边相连。不同的消去方法所得到的分值不同,请设计一种方法得到最大的分值。42+32+22 = 2912+42+32+12 = 27
  • 86. 祖玛游戏
  • 87. 问题表示122233331(1, 1) (2, 3) (3, 4) (1, 1) (a, b)表示b个a颜色的块组成的区域对于一个具有l段的方块行,我们可以用两个长度为l一维数组来表示 color[i]表示第i个区域的颜色 len[i]比奥斯第i区域的长度Color = {1, 2, 3, 1} Len = {1, 3, 4, 1}
  • 88. 分析我们设f[i][j]为消去第i个区域到第j个区域得到的最高得分寻找最优子结构,如何将问题的最优解划为子问题的最优解的组合的形式长度为leng[j]的第j块要不要马上消掉得分 = f[i][j-1] + leng[j] * leng[j]如果要和前面的若干段一起消除,假设若干段中最后一段是q则此时的得分由两部分组成第q+1段到第j-1段可以得到的最高积分 f[q+1][j-1]第i段到第q-1段,以及第q段和第j段组成的新的段的最高得分,但是由于新段大小发生了变化,我们不能再用原来的f[i][q]的形式表示了
  • 89. 最优子结构我们设f[i][j][k]为消去第i个区域到第j-1个区域以及第j个区域和之后的颜色相同的k块合成的区域得到的最高得分得分 = f[i][j-1][0] + leng[j] * leng[j]如果要和前面的若干段一起消除,假设若干段中最后一段是q则此时的得分由两部分组成第q+1段到第j-1段可以得到的最高积分 f[q+1][j-1][0]第i段到第q-1段,以及第q段和第j段组成的新的段的最高得分,f[i][q][k+leng[j]](color[i],leng[i]),(color[i+1],leng[i+1]),……,(color[j-1,leng[j-1]]), (color[j],leng[j]+k)f[i][j][k] = max ( f[i][j-1][0] + leng[j] * leng[j] , f[q+1][j-1][0] + f[i][q][k+leng[j]] ) 其中color[q] = color[j]
  • 90. Problem:括号序列ACM/ICPC Regional Contest Northeast Europe 2001. Problem B
  • 91. 问题描述定义一下序列是规则序列 空序列是规则序列 如果S是规则序列,那么[S]和(S)也是规则序列 如果A、B是规则序列,那么AB也是规则序列 例如下面这些都是规则序列 () 、[] 、 (())、 ([])、 ()[]、 ()[()] 下面几个都不是规则序列 ( 、] 、 )( 、 ([() 现给出由‘(’,‘)’,‘[’,‘]’构成的序列请添加尽量少的括号构造一个规则序列
  • 92. 观察如果S是形如(S’)或[S’],那么只需将S’划为规则的,S就是规则的 如果S是形如(S’,那么只需将S’变成规则的,然后在最后加上一个) S形如[S、S]、S),和上一种情况类似 我们把序列分成两部分Si ….. Sk ,Sk+1…..Sj ,只要将Si ….. Sk和Sk+1…..Sj都变成规则的,那么S就是规则的但是那种方法是添加括号最好的方法呢?找到了问题最优解和子问题最优解之间的关系
  • 93. #define N 100; char a[N]; int bracket(int i, int j) { if(i > j) return 0; else if (i ==j) return 1; int answer = N; if( ( a[i] == '(' && a[j] == ')' ) || ( a[i] == '[' && a[j] == ']' ) ) { answer = min(answer, bracket(i+1, j-1)); else if ( a[i] == '(' || a[i] == '[') answer = min(answer, bracket(i+1, j)+1); else if ( a[j] == ')' || a[j] == ']') answer = min(answer, bracket(i, j-1)+1); for(int k = i; k < j; k++ ) { answer = min(answer, bracket(i,k) + bracket(k+1,j)); } return answer; }   int main() { int minbracket; minbracket = bracket(0, N-1); }简单递归法如果S是形如(S’)或[S’],那么只需将S’划为规则的,S就是规则的 如果S是形如(S’,那么只需将S’变成规则的,然后在最后加上一个) S形如[S、S]、S),和上一种情况类似 我们把序列分成两部分Si ….. Sk ,Sk+1…..Sj ,只要将Si ….. Sk和Sk+1…..Sj都变成规则的,那么S就是规则①② + ③④
  • 94. 观察有什么问题还是存在非常严重的重复计算重叠子问题采用递归记录法开辟一个data[N][N]的数组,用data[i][j],记录Si …..Sj 这个序列需要加入括号的最少个数,这样data[0][N-1]就是我们最后的结果 更容易用来改进原始简单递归算法的性能,需要对源程序改动较小
  • 95. #define N 100; char a[N]; int data[N][N]; //initialize all elements in array data to -1   int bracket(int i, int j) { if(i > j) return 0; else if (i ==j) { data[i][i] = 1; return 1; }else if(data[i][j] >= 0 ) { return data[i][j]; } int answer = N; if( ( a[i] == '(' && a[j] == ')' ) || ( a[i] == '[' && a[j] == ']' ) ) { answer = min(answer, bracket(i+1, j-1)); else if ( a[i] == '(' || a[i] == '[') answer = min(answer, bracket(i+1, j)+1); else if ( a[j] == ')' || a[j] == ']') answer = min(answer, bracket(i, j-1)+1); for(int k = i; k < j; k++ ) { answer = min(answer, bracket(i,k) + bracket(k+1,j)); } data[i][j] = answer; return answer; } 采用递归记录法#define N 100; char a[N]; int bracket(int i, int j) { if(i > j) return 0; else if (i ==j) return 1; int answer = N; if( ( a[i] == '(' && a[j] == ')' ) || ( a[i] == '[' && a[j] == ']' ) ) { answer = min(answer, bracket(i+1, j-1)); else if ( a[i] == '(' || a[i] == '[') answer = min(answer, bracket(i+1, j)+1); else if ( a[j] == ')' || a[j] == ']') answer = min(answer, bracket(i, j-1)+1); for(int k = i; k < j; k++ ) { answer = min(answer, bracket(i,k) + bracket(k+1,j)); } return answer; }
  • 96. 递归记录法的优缺点还是存在非常严重的重复计算重叠子问题采用递归记录法开辟一个data[N][N]的数组,用data[i][j],记录Si …..Sj 这个序列需要加入括号的最少个数,这样data[0][N-1]就是我们最后的结果 更容易用来给进原始简单递归算法的性能,需要对源程序改动较小无法通过递归过程得到除最优解的数值之外的其他信息,例如本题只能得到最少需要加多少个,无法直接得到如何加括号的过程
  • 97. 自底向上法还是存在非常严重的重复计算重叠子问题自底向上方法依次计算 data[i][i](0<=i
  • 98. 101001000100001000001101001000100001000001101001000100001000001101001000100001000001101001000100001000001101001000100001000001
  • 99. char a[N]; int data[N][N]; int minadd; for(int p=1; p
  • 100. 自底向上法在计算data[i][j],如果最小值取自data[i+1][j]则在第j个之后加上和a[i]对应的结束括号,如果最小值取自data[i][j-1]则在第i个之前加上和a[j]对应的开始括号如果S是形如(S’)或[S’],那么只需将S’划为规则的,S就是规则的 如果S是形如(S’,那么只需将S’变成规则的,然后在最后加上一个) S形如[S、S]、S),和上一种情况类似 我们把序列分成两部分Si ….. Sk ,Sk+1…..Sj ,只要将Si ….. Sk和Sk+1…..Sj都变成规则的,那么S就是规则if( ( a[i] == ‘(’ && a[j] == ‘)’ ) || ( a[i] == ‘[’ && a[j] == ‘]’ ) ) { data[i][j] = min(data[i][j], data[i+1, j-1]); else if ( a[i] == ‘(’ || a[i] == ‘[’) data[i][j] = min(data[i][j], data[i+1, j]+1); else if ( a[j] == ‘)’ || a[j] == ‘]’) data[i][j] = min(data[i][j], data[i, j-1]+1); for(int k = i; k < j; k++ ) { data[i][j] = min(data[i][j], data[i,k] + data[k+1,j]); }
  • 101. char a[N]; int data[N][N]; int position[N][N]; int minadd; for(int p=1; p
  • 102. 自底向上法还是存在非常严重的重复计算重叠子问题自底向上方法依次计算 data[i][i](0<=i
  • 103. Problem:格式化文本ACM/ICPC Mid-Central European Regional Contest 1999 http://poj.org/problem?id=1093
  • 104. 问题描述Writings e-mails is fun, but, unfortunately, they do not look very nice, mainly because not all lines have the same lengths. In this problem, your task is to write an e-mail formatting program which reformats a paragraph of an e-mail (e.g. by inserting spaces) so that, afterwards, all lines have the same length (even the last one of each paragraph). The easiest way to perform this task would be to insert more spaces between the words in lines which are too short. But this is not the best way. Consider the following example:**************************** This is the example you are actually considering.**************************** This is the example you are actually considering. **************************** This_is_the_example_you__are actually________considering.**************************** This__is__the__example___you are__actually___considering.Of course, this has to be formalized. To do this, we assign a badness to each gap between words. The badness assigned to a gap of n spaces is (n - 1)^2. The goal of the program is to minimize the sum of all badnesses12+72=501+1+1+4+1+4=12
  • 105. (本页无文本内容)
  • 106. (本页无文本内容)
  • 107. Problem:数组分割问题经典问题