48
3
throw new NoSuchElementException("No Max Element in Empty Array.");
}
return maxElement(vals, 0, vals.length);
}
/**
计算
vals[left, right)
的最大元素
*
注意
vals[right]
并不在计算之列
*/
static int maxElement(int[] vals, int left, int right) {
if (right - left == 1) {
return vals[left];
}
//
计算子问题
int mid = (left + right) / 2;
int max1 = maxElement(vals, left, mid);
int max2 = maxElement(vals, mid, right);
//
合并处理
:
从子问题的解中得到当前问题的解
if (max1 > max2) { return max1; }
return max2;
}
3-2
中分治算法的时间复杂度是
O
(
n
)
,因为子问题解的合并处理在常数时间内就能完
成。如果这一步需要
O
(
n
)
时间,那么整体的时间复杂度将会上升至
O
(
n
log
n
)
。当然
我们也可以不用分治算法,直接遍历数组并且记下当前所找到的最大值。所以,就当是
一个小小的提示吧:分治算法并不总是最快的。
3.6.3 动态规划
动态规划是分治算法的一个衍生,它将一个问题切分成多个更加简单的子问题,然后按
照顺序个解决。对于每个子问题,它只求解一次,然后将结果存储起来以供后续使用
这样可以避免重复计算。此外,动态规划在计算当前解时,
结合
较小规模的子问题的解,
并且不断增加子问题的规模。很多情况下,最终计算出来的解即为全局最优解。
动态规划常用于求解最值优化类问题上。下面通过一个示例来阐释动态规划算法
科学家经常通过比对
DNA
序列来确定其相似性。现有这样一个
DNA
序列——由
A
C
T
G
所组成。因此,一个
DNA
序列就可以使用一个字符串进行表示,而
DNA
序列的相似
性就可以转化成计算两个字符串的
最小编辑距离
。也就是说,给定一个字符串
s
1
和一个
目标字符串
s
2
,需要使用最少的编辑操作来将
s
1
转化成
s
2
。支持的编辑操作包括:
s
1
的一个字符替换成另外一个。
删除
s
1
中的一个字符。
将一个字符插入
s
1
中。
算法基础
49
算法基础
例如字符串
s
1
为“
GCTAC
”,可以通过
3
次编辑操作来得到目标字符串“
CTCA
”:
将第
4
个字符“
A
”换成“
C
”。
删掉第一个字符“
G
”。
将最后一个“
C
”换成“
A
”。
当然还有其他方式来得到目标字符串,但是最少也需要
3
次编辑操作。对于初学者来说,
计算需要操作的次数就已经足够了,我们暂时还不需要计算出具体的操作顺序。
动态规划的关键点是存储子问题的结果。在这个例子中,我们可以使用一个二维矩阵
m
[
i
][
j
]
,来记录
s
1
的前
i
个字符和
s
2
的前
j
个字符之间的最小编辑距离。这个矩阵可以
初始化为:
0 1 2 3 4
1 . . . .
2 . . . .
3 . . . .
4 . . . .
5 . . . .
在这个矩阵中,行标为
i
,列标为
j
。以
m
[0][4]
为例,这个元素表示的是
s
1
的前
0
个字
符(也就是空字符串)和
s
2
的前
4
个字符串(整个字符串
CTCA
”)之间的最小编辑
距离。可以很容易计算出来,
m
[0][4]
的值为
4
,因为我们需要插入全部
s
2
4
个字符到
s
1
中去。同样的,我们也可以轻易得到
m
[3][0]
的值为
3
因为从
s
1
的前
3
个字符来考虑,
我们需要删除这所有
3
个字符来得到
s
2
的前
0
个字符(即空字符串)。
动态规划的巧妙之处在于如何不断地从规模较小的子问题的解中构建出当前的最优解。
让我们来看看
m
[1][1]
,这是表示
s
1
的第一个字符
G
s
2
的第一个字符
C
之间的编辑
距离,现在有
3
个选择:
将“
G
”替换为“
C
”,需要
1
次操作。
将“
G
”删除,然后入“
C
”,需要
2
次操作。
插入“
C
”,然后将“
G
”删除,需要
2
次操作。
我们肯定选择操作数最小的,所以
m
[1][1]=1
。那么怎么推广这个选择策略呢?试考虑
3-2
所示的计算过程
50
3
每一次计算
m
[
i
][
j
]
时都面临
3
个选择:
替换代价
计算出
s
1
的前
i
1
个字符和
s
2
的前
j
1
个字符
之间的最小编辑距离,然后如果
s
1
[
i
]
不等于
s
2
[
j
]
m
[
i
][
j
] =
m
[
i
1][
j
1] + 1
,否则
m
[
i
][
j
] =
m
[
i
1][
j
1]
删除代价
计算出
s
1
的前
i
1
个字符和
s
2
的前
j
个字符之间的最小编辑距离,然后删掉
s
1
i
个字符,操作数加
1
插入代价
计算出
s
1
的前
i
个字符和
s
2
的前
j
1
个字符之间的最小编辑距离,在此基础上需
要插入
s
2
的第
j
个字符,所以操作数加
1
现在我们脑海里面就应该有一幅图片,生动地描述了动态规划是如何一步一步地按照既
定的顺序从小规模的子问题开始逐渐处理的(,从第一行到最后一行,每行按照最左
到最右的顺序访问,如例
3-3
所示)。计算过程是按照行标
i
1
len
(
s
1
)
逐渐进行。
当矩阵
m
初始化之后,我们利用嵌套的
for
循环计算每个子问题的最优解,直到
m
的所有值都已经计算完毕。这个过程通常不用递归,而是会将之前计算过的结果存储起
来。最终的最优解即为
m
[
len
(
s
1
)][
len
(
s
2
)]
的值。
༺࣑
෸أ
֭෇
پॏ
ፌၭኵ
༺࣑پॏ
෸أپॏ
֭෇پॏ
i j
m
m
m
m
i
i
i
j
j
j
پॏ
i
i
j
j
3-2:计算
m
[
i
][
j
]
算法基础
51
算法基础
3-3
:使用动态规划计算最小编辑距离(
Python
def minEditDistance(s1, s2):
"""
计算将
s1
转换到
s2
的最小编辑距离
"""
len1 = len(s1)
len2 = len(s2)
#
创建一个二维结构
#
满足
m[i][j] = 0, 0
i
len1, 0
j
len2
m = [None] * (len1 + 1)
for i in range(len1 + 1):
m[i] = [0] * (len2 + 1)
#
横向纵向设置初始化操作次数
for i in range(1, len1 + 1):
m[i][0] = i
for j in range(1, len2 + 1):
m[0][j] = j
#
计算最优解
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost = m[i - 1][j - 1] + cost
removeCost = m[i - 1][j] + 1
insertCost = m[i][j - 1] + 1
m[i][j] = min(replaceCost, removeCost, insertCost)
return m[len1][len2]
3-5
给出了矩阵
m
的最终值。
3
-
5
:所有子问题的解
0 1 2 3 4
1 1 2 3 4
2 1 2 2 3
3 2 1 2 3
4 3 2 2 2
5 4 3 2 3
例如
m
[3][2]=1
,因为字符串“
GCT
”和“
CT
”的最小编辑距离只有
1
,仅仅需要删掉
GCT
的第一个字符即可。这段代码仅仅计算了最小编辑距离,如果需要记录操作顺序,
那么就需要另外一个矩阵
prev
来存储。
prev
[
i
][
j
]
记录了在计算
m
[
i
][
j
]
时所选择的
3
操作中的哪一个。要恢复操作,我们可以从
m[
len
(
s
1
)][
len
(
s
2
)]
开始,使用
prev
[
i
][
j
]
的值,
一步一步地向后追溯,直到
m
[
0
][
0
]
为止。修改过的代码见例
3-4
52
3
3-4
:使用动态规划计算最小编辑距离,并且记录操作顺序
REPLACE = 0
REMOVE = 1
INSERT = 2
def minEditDistance(s1, s2):
"""
计算将
s1
转换到
s2
的最小编辑距离,并且记录操作顺序
"""
len1 = len(s1)
len2 = len(s2)
#
创建一个二维结构
#
满足
m[i][j] = 0, 0
i
len1, 0
j
len2
m = [None] * (len1 + 1)
op = [None] * (len1 + 1)
for i in range(len1 + 1):
m[i] = [0] * (len2 + 1)
op[i] = [-1] * (len2 + 1)
#
横向
纵向设置初始化代价
for j in range(1, len2 + 1):
m[0][j] = j
for i in range(1, len1 + 1):
m[i][0] = i
#
计算最优解
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
cost = 1
if s1[i - 1] == s2[j - 1]: cost = 0
replaceCost = m[i - 1][j - 1] + cost
removeCost = m[i - 1][j] + 1
insertCost = m[i][j - 1] + 1
costs = [replaceCost, removeCost, insertCost]
m[i][j] = min(costs)
op[i][j] = costs.index(m[i][j])
ops = []
i = len1
j = len2
while i != 0 or j != 0:
if op[i][j] == REMOVE or j == 0:
ops.append('remove {}-th char {} of {}'.format(i,s1[i-1],s1))
i = i - 1
elif op[i][j] == INSERT or i == 0:
ops.append('insert {}-th char {} of {}'.format(j,s2[j-1],s2))
j = j - 1
else:
if m[i - 1][j - 1] < m[i][j]:
fmt='replace {}-th char of {} ({}) with {}'
ops.append(fmt.format(s1, i, s1[i - 1], s2[j - 1]))
i, j = i - 1, j - 1
return m[len1][len2], ops

Get 算法技术手册(原书第2 版) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.