算法设计 动态规划设计.pptVIP

T(1,{2,3,4}) T(2,{3,4}) T(3,{2,4}) T(4,{2,3}) T(3,{4}) T(4,{3}) T(2,{4}) T(4,{2}) T(2,{3}) T(3,{2}) T(4,Φ) T(3,Φ) T(4,Φ) T(2,Φ) T(3,Φ) T(4,Φ) T(1,{2,3,4,5}) T(2,{3,4,5}) T(3,{2,4,5}) T(3,{4,5}) T(4,{5}) T(5,{4}) T(2,{4,5}) T(5,{4}) T(4,{5}) T(1,{2,3,4}) T(2,{3,4}) T(3,{2,4}) T(4,{2,3}) T(3,{4}) T(4,{3}) T(2,{4}) T(4,{2}) T(2,{3}) T(3,{2}) T(4,Φ) T(3,Φ) T(4,Φ) T(2,Φ) T(3,Φ) T(4,Φ) 1 (n-1) C(n-2,n-2) (n-1) C(n-2,n-3) 第k层 (n-1) C(n-2,n-k-1) n-1 一共 层 第k层 (n-1) C(n-2,n-k-1) ；一共n-1层 1+ Σ(n-1) C(n-2,n-k-1) k＝1 n-1 k＝1 = 1+ (n-1) ΣC(n-2, ) n-1 = 1+ (n-1) ΣC(n-2, ) k＝0 n-2 k-1 k 2n=1+C(n,1)+ C(n,2)+…+ C(n,n) = ΣC(n, k) k＝0 n =1+(n-1)2n-2 空间复杂性 O(n2n) 矩阵链乘法 问题描述 加括号的方案数 动态规划法 矩阵链乘法: 问题描述 给定n个矩阵A1,A2,…, An，Ai的维数为pi-1×pi(1≤i≤n), 要求计算连乘积A1A2… An 由于矩阵乘法满足结合率，所以可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。 比如： A1,A2,A3,A4 (A1 ( A2 ( A3 (A4) ) ) (A1 (( A2 A3 ) A4 ) ) (A1 A2 )( A3 A4 ) (( A1 ( A2 A3) ) A4 ) (( A1 A2 ) A3) A4 ) 不同的计算次序有不同的计算量 注： 1.设Ap×q,Aq×r两矩阵相乘，普通乘法的次数为p×q×r 2.加括号对乘法次数的影响 如：A10×100×B100×5×C5×50 ((AB)C): 10×100×5+10×5×50=7500次 (A(BC)): 100×5×50+10×100×50=75000次 穷举法： 将n个矩阵从第k和第k+1处隔开，对二个子序列再分别加括号，则可以得到下面递归式： 因此，穷举法不是一个有效算法 计算m[1][4]过程如下： 自顶向下递归求解最优解的值 如A[3:4]被计算了2次，保存下来可以节省许多时间 matrixChain(int [] p, int [][] m, int [][] s) { int n=p.length-1; for (int i = 1; i = n; i++) m[i][i] = 0; for (int r = 2; r = n; r++) for (int i = 1; i = n - r+1; i++) { int j=i+r-1; m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k j; k++) { int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; if (t m[i][j]) { m[i][j] = t; s[i][j] = k;} } } } 矩阵链乘法:动态规划算法 自底向上记忆化方式求解m[i][j] - 计算方向： j m[1][1], m[1][2], m[1][3], … , m[1][n] m[2][2],