清华大学出版社 TSINGHUA UNIVERSITY PRESS 二、重叠子问题 递归算法求解问题时,每次产生的子问题并不总是新问题,有 些子问题被反复计算多次。这种性质称为子问题的重叠性质 动态规划算法,对每一个子问题只解一次,而后将其解保存在 个表格中,当再次需要解此子问题时,只是简单地用常数时 间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动 态规划算法只需要多项式时间,从而获得较高的解题效率。 4;4 面的四面面以购回函囪 A223: 16
16 二、重叠子问题 •递归算法求解问题时，每次产生的子问题并不总是新问题，有 些子问题被反复计算多次。这种性质称为子问题的重叠性质。 •动态规划算法，对每一个子问题只解一次，而后将其解保存在 一个表格中，当再次需要解此子问题时，只是简单地用常数时 间查看一下结果。 •通常不同的子问题个数随问题的大小呈多项式增长。因此用动 态规划算法只需要多项式时间，从而获得较高的解题效率
清华大学出版社 TSINGHUA UNIVERSITY PRESS 三、备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同,区别 在于备忘录方法为每个解过的子问题建立了备忘录以备需要时 查看,避免了相同子问题的重复求解。 m0 private static int lookup Chain (int i, int D if(m00]>0)return m[ol if (i==j return 0 int u= lookupchain(i+1,j)+ p[]*p0*pr s00]=i for(int k=i+1; k<j; k++)i int t= lookup chain (i, k)+ lookup Chain(k+1,)+ p[i-1]*p[k]"pjl if (t <u)t u=t; s[0]=k; return u 17
17 三、备忘录方法 •备忘录方法的控制结构与直接递归方法的控制结构相同，区别 在于备忘录方法为每个解过的子问题建立了备忘录以备需要时 查看，避免了相同子问题的重复求解。 m0 private static int lookupChain(int i, int j) { if (m[i][j] > 0) return m[i][j]; if (i == j) return 0; int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = lookupChain(i,k) + lookupChain(k+1,j) + p[i-1]*p[k]*p[j]; if (t < u) { u = t; s[i][j] = k;} } m[i][j] = u; return u; }