算法导论14.4 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

14.4-1

实际上，一共有\(8\)个符合要求的子序列，这些子序列的长度为\(6\)。

\(\begin{aligned} \langle0,0,1,0,1,0\rangle \\ \langle0,0,1,0,1,1\rangle \\ \langle0,0,1,1,0,1\rangle \\ \langle0,1,0,1,0,1\rangle \\ \langle1,0,0,1,1,0\rangle \\ \langle1,0,1,0,1,0\rangle \\ \langle1,0,1,0,1,1\rangle \\ \langle1,0,1,1,0,1\rangle \\ \end{aligned}\)

14.4-2

1
2
3
4
5
6
7
8
9
10
11
12
13
RECONSTRUCT-LCS(c, X, Y, m, n)
  k = c[m, n]
  let l[1 : k] be a new array
  while m > 0 and n > 0
    if X[m] == Y[n]
      l[c[m, n]] = X[m]
      m = m - 1
      n = n - 1
    else if c[m, n] == c[m - 1, n]
      m = m - 1
    else
      n = n - 1
  return l

14.4-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
MEMOIZED-LCS-LENGTH(X, Y, i, j, b, c)
  if i == 0 or j == 0
    c[i, j] = 0
    return 0
  else if c[i, j] != -1
    return c[i, j]
  else
    if X[i] == Y[j]
      c[i, j] = MEMOIZED-LCS-LENGTH(X, Y, i - 1, j - 1, b, c) + 1
      b[i, j] = "↖"
    else
      u = MEMOIZED-LCS-LENGTH(X, Y, i - 1, j, b, c)
      l = MEMOIZED-LCS-LENGTH(X, Y, i, j - 1, b, c)
      if u >= l
        c[i, j] = u
        b[i, j] = "↑"
      else
        c[i, j] = l
        b[i, j] = "←"
    return c[i, j]

14.4-4

为了尽量减少元素使用量，如果\(m< n\)，那么交换字符串\(X,Y\)再运行程序。这并不影响它们的LCS长度。

可以发现，由于\(c[i,j]\)只从\(c[i-1,j],c[i-1,j-1],c[i,j-1]\)中的一个状态转移过来，这些状态只从在当前行或者上一行，因此我们只需要保存两行的\(c\)表即可。

计算\(c[i,j]\)时，如果只希望保存一行元素，那么针对上一行的元素两个元素\(c[i-1,j-1],c[i-1,j]\)分别进行如下处理：

  • 用一个临时遍历临时存储\(c[i-1,j-1]\)。

  • \(c[i-1,j]\)的值仍然未被覆盖，可以直接使用。

这两个版本的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
LCS-LENGTH1(X, Y, m, n)
  if m < n
    swap X with Y
    swap m with n
  let c[0 : 2, 0 : n] be new table
  for j = 0 to n
    c[0, j] = 0
  c[1, 0] = 0
  for i = 1 to m
    for j = 1 to n
      if X[i] == Y[j]
        c[i mod 2, j] = c[1 - (i mod 2), j - 1] + 1
      else
        c[i mod 2, j] = max{c[i mod 2, j - 1], c[1 - (i mod 2), j]}
  return c[m mod 2, n]

LCS-LENGTH2(X, Y, m, n)
  if m < n
    swap X with Y
    swap m with n
  let c[0 : n] be new array
  for j = 0 to n
    c[j] = 0
  for i = 1 to m
    prev = c[0]
    for j = 1 to n
      temp = c[j]
      if X[i] == Y[j]
        c[j] = p + 1
      else
        c[j] = max{c[j - 1], c[j]}
      prev = temp
  return c[n]

14.4-5

假设\(X[0]=-\infty\)，以使得所有\(X[i]\)都可以接在它后面，实际上，\(X[0]\)并不存在。对于每一个数\(X[i]\)，如果\(j< i\)并且\(X[j]\le X[i]\)，那么如果一个序列以\(X[j]\)为结尾，添加上\(X[i]\)后，那么变成了以\(X[i]\)为结尾的序列，并且长度增加了\(1\)。令\(c[i]\)为以\(X[i]\)为结尾的子序列的最长长度，那么根据最优子结构，可以写出如下状态转移方程：

\(c[i]= \left \{\begin{aligned} &0 & & \text{if}\quad i=0 \\ &\max_{0\le j<i,X[j]\le X[i]}\{ f[j]+1\}& & \text{if}\quad i>0 \\ \end{aligned}\right.\)

按照这个状态转移方程可以写出子程序LIS-LENGTH：

1
2
3
4
5
6
7
8
9
10
11
12
LIS-LENGTH(X, m)
  let c[0 : m] be new array
  X[0] = −∞
  for i = 0 to m
    f[i] = 0
    for j = 0 to i - 1
      if X[j] <= X[i]
        f[i] = max{f[i], f[j] + 1}
  q = 0
  for i = 1 to m
    q = max{q, f[i]}
  return q

\(\star\) 14.4-6

1
2
3
4
5
6
7
8
9
10
11
LIS-LENGTH(X, m)
  let a[1 : m] be new array
  n = 0
  for i = 1 to m:
    if n == 0 or X[i] >= a[n]
      n += 1
      a[n] = X[i]
    else
      let j ∈ [1, 2, ..., n] be the largest index s.t. a[j] > X[i]
      a[j] = X[i]
  return n

基本思想：如果我们得到了一个不下降子序列，那么我们希望最后一个数尽可能的小，以使以后转移时当前状态有更大的机会。数组\(a[i]\)表示长度为\(i\)的最长上升子序列中，第\(i\)个数能达到的最小值。如第8行中的代码，如果找到了符合条件的\(j\)，那么说明\(a[j-1]\le X[i]\)，那么\(X[i]\)可以拼接在\(a[j-1]\)的后面，从而得到一个长度为\(j\)的不下降子序列。

迭代完成后，\(n\)就是能够得到最长的不下降子序列长度。由于数组\(a\)一直是单调递增的，因此第8行代码在寻找j的过程可以以\(\Theta(\lg n)\)的时间完成。

最终，整个算法的时间复杂度为\(O(n \lg n)\)。