算法导论14.4 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 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 j0 \
\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)$。