Blog - wingsico

什么是动态规划

一个问题具有最优子结构,且每一个解也是最优的,那么求得的即是最优解。

动态规划只适用于具有最优子结构的问题。而最优子结构表示的是局部的最优解可以决定全局的最优解,而更简单的说法即是:问题可以分成更小的小问题。听起来跟分治法有些类似,这里做一个简单的区分:

分治法主要是将原问题划分成一个个独立的子问题,递归地对子问题进行求解之后,将每个子问题的结果进行合并而得到原问题的解。主要步骤是:

  1. 分解
  2. 解决
  3. 合并

动态规划与分治法不同,动态规划适用于子问题独立且重叠的问题,重叠的意义在于每个子问题都包含一部分相同的子子问题,动态规划会对这些子子问题求解且只求解一次并且保存在表中,当需要使用到公共部分时直接从表中取而避免重复计算。

动态规划中包含两个主要要素:

  1. 最优子结构
  2. 重叠子问题

最优子结构:如果一个问题的最优解包含了其子问题的最优解,那么该问题具有最优子结构。

重叠子问题:在两个不同的子问题中,如果他们是相同的子问题,只是作为不同问题的子问题提出时,他们是重叠的。且动态规划中对于重叠的子问题不再重复计算,而是从固定空间中取出之前已经求得的子问题解。

动态规划求解步骤:

  1. 划分最优化问题,找出最优解性质,刻画其结构特性
  2. 构造状态表示,确定递推/递归关系,确定边界条件
  3. 按自底向上的方式计算最优解的值

若需要求得最优解,则需要根据计算结果的表格来构造最优解。

LCS(Longest Common Subsequence)问题

问题描述

如果一个序列Seq1按照其字母出现的顺序出现在另一个序列Seq2上,那么称该序列Seq1为另一个序列Seq2的子序列。

PS:Seq1中的字母并不需要连续的出现在Seq2中。

问题:给出两个序列,要求求出它们的最长公共子序列。

例如:给出序列 Seq1: abcbdab 和 序列 Seq2: bdcaba, 其最长公共子序列为: bcab (不唯一,给出一个即可)

求解思路

1. 刻画最优子结构

假设 $X_i$ 表示序列 $X$ 的前 $i$ 个字母组成的子序列,$Y_j$ 表示序列 $Y$ 的前 $j$ 个字母组成的子序列。且 $Z$ 为 $X, Y$ 的最长公共子序列。$x_i$ 表示序列 $X$ 的第 $i$ 个字符,$y_j$ 表示序列 $Y$ 的第 $j$ 个字符。$k$ 为 $Z$ 的长度。

限制条件:$i<=m, j<=n$(其中 $m$ 是 $X$ 的长度,$n$ 是 $Y$ 的长度)

那么有如下几种情况:

  • 如果 $x_m=y_n$,那么两个序列的最后一个字符一定是最长公共子序列 $Z$ 的最后一个字符,即 $x_m=y_n=z_k$。此时已经确定最后一个字符,那么问题化归为求解 $Z_{k-1}$,且 $Z_{k-1}\in LCS(X_{m-1},Y_{n-1})$。此时 $Z_{k-1}$ 是 $X_{m-1}, Y_{n-1}$ 的公共最长子序列。

  • 如果 $x_m \ne y_n$,那么要么 $Z \in LCS(X_{m-1}, Y)$,要么 $Z \in LCS(X, Y_{n-1})$,问题化归为求解 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$。

由于第二点中 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$ 不相互独立,都需要求解 $LCS(X_{m-1}, Y_{n-1})$,具有最优子结构性质,故使用动态规划法求解。

2. 确定递推/递归关系式

由最优子结构性质可知,若要求 $X,Y$ 的最长公共子序列,则按如下方式进行递推式求解:

当 $x_m=y_n$,$LCS(X,Y)$ 就是 $LCS(X_{m-1}, Y_{n-1})$ 再在尾部加上 $x_m$ 或 $y_n$。

当 $x_m \ne y_n$,那么要解决两个子问题,即找出 $LCS(X_{m-1}, Y)$ 和 $LCS(X, Y_{n-1})$,且其中更长的为 $LCS(X,Y)$,即 $Max(LCS(X_{m-1}, Y),LCS(X, Y_{n-1}))$

由此递推结构容易看到最长公共子序列问题具有子问题重叠性质,都需要求解 $LCS(X_{m-1}, Y_{n-1})$。

利用 $record[i][j]$ 来记录 $X_i, Y_j$ 的最长公共子序列的长度。

边界条件:当 $i$ 或 $j$ 为 $0$ 时,空序列是 $X, Y$ 的最长子序列,即 $record[i][j] = 0$,其他递推关系如下:

3. 求解最优值

根据上面给出的递推关系以及边界条件,很容易写出相关代码:

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
35
36
37
38
39
40
41
42
function LCS(str1 = '', str2 = '') {
if (!str1 || !str2) {
return 0;
}

const len1 = str1.length;
const len2 = str2.length;

if (!len1 || !len2) {
return 0;
}

// LCS 长度记录
let record = new Array(len1 + 1).fill([]).map(k => []);

// 初始化 记录表
for (let i = 0; i <= len1; i++) {
record[i][0] = 0;
}

for (let j = 0; j <= len2; j++) {
record[0][j] = 0;
}

// 自底向上求解
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
let ch1 = str1.charAt(i - 1);
let ch2 = str2.charAt(j - 1);

if (ch1 === ch2) {
record[i][j] = record[i - 1][j - 1] + 1;
} else if (record[i - 1][j] >= record[i][j - 1]) {
record[i][j] = record[i - 1][j]
} else {
record[i][j] = record[i][j - 1]
}
}
}

console.log(`Length: ${record[len1][len2]}`);
}

以上算法的时间复杂度为 $O(mn)$

4. 构造最优解

未完待续

 评论