钢条切割 令r(m为长度为n英寸的钢条的最大收益,则 r(n=maxpitr(n-Of 1≤i≤n 含义:从一端切一段长度为钢条下来后,可获得的最大收益 即切下来的钢条价格pi,加上剩下长度为n的钢条的最大收益 具有最优子结构: 问题的最优解包括子问题最优解 16
钢条切割 ◼ 令r(n)为长度为n英寸的钢条的最大收益，则 16 𝒓 𝒏 = 𝐦𝐚𝐱 𝟏≤𝒊≤𝒏 {𝒑𝒊 + 𝒓(𝒏 − 𝒊)} 含义：从一端切一段长度为i的钢条下来后，可获得的最大收益 即切下来的钢条价格pi，加上剩下长度为n-i的钢条的最大收益 具有最优子结构： 问题的最优解包括子问题最优解
钢条切割 令r(m为长度为n英寸的钢条的最大收益,则 r(n=maxpitr(n-Of 1≤i≤n rin r(n-2 r(n-3) 0) 具有子问题重叠性 r(n-2)r(n-3)…:r(0) 17
钢条切割 ◼ 令r(n)为长度为n英寸的钢条的最大收益，则 17 𝒓 𝒏 = 𝐦𝐚𝐱 𝟏≤𝒊≤𝒏 {𝒑𝒊 + 𝒓(𝒏 − 𝒊)} 具有子问题重叠性 r(n) r(n-1) r(n-2) r(0) r(n-2) r(n-3) r(n-3) … r(0) …
钢条切割 自底向上方法 CUT(P, n, r) r|0]=0 for i=l to n temp for i=l to j temp=max(temp, pi+rlij-i) temp r0]不用计算,依次计算r[1r2r3]r4] 18
钢条切割 18 CUT(p, n, r) r[0] = 0 for j=1 to n temp = -∞ for i=1 to j temp = max(temp, p[i]+r[j-i]) r[j] = temp 自底向上方法 r[0]不用计算，依次计算r[1],r[2],r[3],r[4]
钢条物割 递归备忘录方法 预处理r],使r[i=-00 CUT(p, n, r) frln0 then return r[nWrm不用重复计算了 if n==0 then temp=0 else temp for i=l to n do temp=max(temp, p+ CUT(p, n-i)) rIn= tem Ip return temp 19
钢条切割 19 预处理r[ ]，使r[i]=-∞ CUT(p, n, r) if r[n]≥0 then return r[n] if n == 0 then temp = 0 else temp = -∞ for i=1 to n do temp = max(temp , p[i]+CUT(p, n-i)) r[n] = temp return temp 递归备忘录方法 //r[n]不用重复计算了
最长公共子序列 子序列 口X=<x1x2,…,Xn>,若1i<2<…ik≤m,使z=< z1z2",z>=<X1,x2,x>,称Z是X的子序列 XE(A,B,C, D, E,F, G) z=(B,C,E,F是X的子序例 W=(B,D,A不是X的子序例 ■公共子序列 口Z是序列X与Y的公共子序列 >Z是X的子序列 >Z也是Y的子序列 20
最长公共子序列 ◼ 子序列 X=<x1 , x2 , … , xm>, 若1≤i1<i2< ┅ <ik≤m，使Z=< z1 , z2 , ┅ , zk> = <xi1, xi2, ┅ , xik>, 称Z是X的子序列 ➢ X=(A, B, C, D, E, F, G) ➢ Z=(B, C, E, F)是 X 的子序例 ➢ W=(B, D, A)不是X的子序例 ◼ 公共子序列 Z 是序列 X 与 Y 的公共子序列 ➢ Z 是X的子序列 ➢ Z 也是Y的子序列 20