葫芦岛23点

1. 钢条切割
2. 矩阵链乘法
   1. 构造最优解
3. 最长公共子序列
   1. 构造最优解
4. 最长上升子序列
5. 最优二叉搜索树

钢条切割

给定一段长度为n英寸的钢条和一个价格表p_i，求切割钢条方案，使得销售收益r_s最大。如果长度为n英寸的钢条的价格p_n足够大，最优解可能就是完全不需要切割。
长度为n英寸的钢条共有 2¯(n-1)种不同的切割方案，因为在距离钢条左端i英寸处总是可以选择切不切，如果要求按切割数量非递减的顺序切割，切割方案会少很多，近似等于e¯(x√(2n/3))/4n√3，但仍远远大于任何n的多项式。
应用递归式r[n]=max(1<=i<=n)->(p[i]+r[n-i])将一个指数时间的解转化为一个多项式时间的解，时空权衡【time-memory trade-off】。

矩阵链乘法

1
2
3
4
5
6
7
8
9
10

MATRIX-MULTIPLY(A,B)
   if A.columns!=B.rows
      error "incompatible dimensions"
   else let C be a new A.rows*B.columns matrix
      for i=1 to A.rows
         for j=1 to B.columns
            C[i,j]=0
            for k=1 to A.columns
               C[i,j]=C[i,j]+A[i,k]*B[k,j]
   return C

给定n个矩阵的链，矩阵A_i的规模为p_i-1*p_i(1<=i<=n)，求完全括号化方案，使得计算A_1A_2…A_n所需标量乘法次数最少。完全括号化【fully parenthesized】指的是单一矩阵或者是两个完全括号化的矩阵乘积链的积，且已外加括号。
穷举所有括号化方案会得到递归式P(n)={1若n=1|∑k=1to(n-1)->P(k)P(k-n)若n>=2}，Ω(2¯n)相似的递归公式产生的序列为卡特兰数【catalan numbers】，这个序列的增长速度为Ω(4¯n/n¯(3/2))。
应用递归式m[i,j]={0若i=j|min(i<=k<j)->(m[i,k]+m[k+1,j]+p_(i-1)p_kp_i)若i<j}完成Ω(n¯2)的算法。

构造最优解

1
2
3
4
5
6
7

PRINT-OPTIMAL-PARENS(s,i,j)
   if i==j
      print 'A'_i
   else print '('
      PRINT-OPTIMAL-PARENS(s,i,s[i,j])
      PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)
      print ')'

最长公共子序列

给定两个序列X和Y，如果Z既是X的子序列，也是Y的子序列，那么称Z是X和Y的公共子序列【common subsequence】。以Z的长度作为X和Y的相似度，那么相似度最高的序列被认为是最长公共子序列【longest common subsequence】。
应用递归式c[i,j]={0若i=0或j=0|c[i-1,j-1]+1若i,j>0且x_i=y_j|max(c[i,j-1],c[i-1,j])若i,j>0且x_i≠y_i}。

构造最优解

1
2
3
4
5
6
7
8
9

PRINT-LCS(c,X,i,j)
   if i==0 or j==0
      return
   if c[i,j]==c[i-1,j-1]
      PRINT-LCS(c,X,i,j)
      print x[i]
   elseif c[i,j]==c[i-1,j]
      PRINT-LCS(c,X,i-1,j)
   else PRINT-LCS(c,X,i,j-1)

最长上升子序列

应用递归式c[i]={max(1<=j<i)->(c[j]+1)若x[i]>x[j]}完成O(n¯2)的算法。
一个长度为i的候选子序列的尾元素至少不比一个长度为i-1候选子序列的尾元素小。可得O(nlgn)算法。

1
2
3
4
5
6
7
8
9
10

l[1]=x[1]
for i=2 to m
   if x[i]<l[1]
      l[1]=x[i]
   elseif x[i]>l[j]
      l[j+1]=x[i]
      sz++
   else
      k=binary_search(l,sz,x[i])
      l[k]=x[i]

最优二叉搜索树

假定我们正在设计一个程序，实现英语文本到法语的翻译。对英语文本中出现的每个单词，我们需要查找对应的法语单词。为了实现这些查找操作，可以创建一棵二叉搜索树，将n个英语单词作为关键字，对应的法语单词作为关联数据。由于文本中的每个单词都要进行搜索，我们希望花费在搜索上的总时间尽量少。
通过红黑树或其他平衡搜索树结构，我们可以假定每次搜索时间为O(lgn) 。但由于单词出现的频率是不同的，像“the”这种频繁使用的单词有可能位于搜索树中远离根的位置上，而像“machicolation”这种很少使用的单词可能位于靠近根的位置上。这样的结构会减慢翻译的速度，因为二叉树搜索树中搜索一个关键字的权重是深度+1。我们希望文本中频繁出现的单词被置于靠近根的位置。在给定单词出现频率的前提下，我们应该如何组织一棵二叉搜索树，使得所有搜索操作访问的结点总数最少呢？
递归式e[i,j]={q_(i-1)若j=i-1|min(i<=r<=j)->(e[i,r-1]+e[r+1,j]+w[i,j])若i<=j}。