@zqbinggong
2018-03-21T20:53:43.000000Z
字数 3072
阅读 1072
动态规划
矩阵链乘法
LCS
算法导论
刻画子问题空间的好经验是:保持子问题空间尽可能简单,只有在必要时才扩展它
具体实现,自顶向下和自底向上———。前者需要一个备忘机制,来存储已经求得的子问题的解,后者则不需要
自顶向下
Memoized-cut-rod(p,n)
let r[0...n] and s[0...n] be new arrays
for i = o to n
r[i] = -00
(val,s) = memoized-cut-rod-aux(p,n,r,s)
print val
while n > 0
print s[n]
n = n - s[n]
memoized-cut-rod-aux(p,n,r,s)
if r[n] >= 0
return r[n]
if n == 0
q = 0
else q = -00
for i = 1 to n
(val,s) = memoized-cut-rod-aux(p,n-i,r,s)
if q < p[i] + val
q = p[i] + val
s[n] = i
r[n] = q
return (q,s)
自底向上
bottom-up-cut-rod(p,n)
(r,s) = extended-bottom-up-cut-rod(p,n)
print r
while n > 0
print s[n]
n = n - s[n]
extended-bottom-up-cut-rod(p,n)
let r[0...n] and s[0...n] be new arrays
r[0] = 0
for j = 1 to n #棒长
q = -00
for i = 1 to j #切割的位置
` if q < p[i] + r[j-i]
q = p[i] + r[j-i]
s[j] = i
r[j] = q
return (q,s)
matrix-chain-orger(p)
n = p.length - 1
let m[1...n,1...n] and s[1...n-1,2...n] be new arrays
for i = 1 to n
m[i,i] = 0
for l = 2 to n #子序列的长度
for i = 1 to n-l+1 #开始位置
j = i + l - 1 #结束位置,j-i+1 = l
m[i,j] = 00
for k = i to j-1 #划分点位置
q = m[i,k] + m[k+1,j] + p[i-1]p[k]p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s
print-optimal-parens(s,i,j)
if i == j
print"A"
else
print "("
print-optimal-parens(s,i,s[i,j])
print-optimal-parens(s,s[i,j]+1,j)
pritn ")"
lcs-length(X,Y)
m = X.length
n = Y.length
let b[1...m,1...n] and c[0...m,0...n] be new tables
for i = 1 to m
c[i,0] = 0
for j = 0 to n
c[0,j] = 0
for i = 1 to m
for j = 1 to n
if X[i] == Y[j]
c[i,j] = c[i-1,j-1] + 1
b[i,j] = 0
else if c[i-1,j] >= c[i-1,j]
c[i,j] = c[i-1,j]
b[i,j] = 1
else
c[i,j] = c[i,j-1]
b[i,j] = -1
return c and b
print-lcs(b,X,i,j)
if i == 0 or j == 0
return
if b[i,j] == 0
print-lcs(b,X,i-1,j-1)
print x[i]
else if b[i,j] == 1
print-lcs(b,X,i-1,j)
else
print-lcs(b,X,i,j-1)
递推关系式:
其中
此处需要注意的是多加的概率项,这是因为把一棵树作为嫁接到另一棵树的根结点时,该子树每个结点的高度要加1
optimal-bst(p,q,n)
let e[1...n+1,0...n] and w[1...n+1,0...n] and root[1...n,1...n]
for i = 1 to n+1
e[i,i-1] = q[i-1]
w[i,i-1] = q[i-1]
for l = 1 to n
for i = 1 to n-l+1
j = i + l - 1
e[i,j] = 00
w[i,j] = w[i,j-1] + p[i] + q[j]
for r = i to j
t = e[i,r-1]+e[r+1,j]+w(i,j)
if t < r[i,j]
e[i,j] = t
root[i,j] = r
return e and root
construct-optimal-bst(root)
r = root[1,n]
print "k"r "is the root"
construct-opt-subtree(1,r-1,r,"left",root)
construct-opt-subtree(r+1,n,r,"right",root)
construct-opt-subtree(i,j,r,dir,root)
if i <= j
t = root[i,j]
print "k"t "is" dir "child of k"r
construct-opt-subtree(1,t-1,t,"left",root)
construct-opt-subtree(t+1,n,t,"right",root)