###最长递增子序列问题(Longest Increasing Subsequence)

Given a sequence of integers, find the longest increasing subsequence (LIS).

这个问题有两种解法:

####解法一
令dp[i]表示以nums[i]结尾的递增子序列长度,那么dp[i+1] = max{dp[j], j < i, nums[j] <= nums[i]} + 1

时间复杂度为$O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size(), 0);
int result = 0;
for (int i = 0; i < nums.size(); i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] >= nums[j])
dp[i] = max(dp[i], dp[j] + 1);
}
result = max(result, dp[i]);
}
return result;
}
};

####解法二
这个方法比较巧妙,我们使用一个数组K,令K[i]表示长度为i的递增子序列的末尾的最小值,比如说有两个递增子序列3,43,5那么K[i]存的应该是4

然后我们就可以在K中二分查找第一个大于nums[i]的值,有三种可能,

  • 第一种就是K中每一个都比它大,那么它就自己可以形成一个长度为1的递增子序列,同时更新K[0]的值。
  • 第二种就是能在K的中间找到一个值j,如果nums[i] < j,更新K中的值为nums[i]
  • 第三种就是没有一个比它大的,那么这时就可以更新最长子序列的长度,并将K[L]的值设为nums[i]

在代码中,我们将K中存储的换为数字在nums中的下标。

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
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.size() == 0) return 0;
vector<int> K(nums.size() + 1, 0);
int L = 1;
for (int i = 1; i < nums.size(); i++) {
int j = find(nums, K, L, i);
if (j == L || nums[K[j]] > nums[i]) {
L = max(j + 1, L);
K[j] = i;
}
}
return L;
}
int find(vector<int> &nums, vector<int> &K, int L, int pos) {
int lb = -1, ub = L;
while (ub - lb > 1) {
int mid = lb + (ub - lb) / 2;
if (nums[K[mid]] > nums[pos])
ub = mid;
else
lb = mid;
}
return ub;
}
};

###最长公共子串问题

Given two strings, find the longest common substring.

最长公共字串与最长公共子序列不同,字串必须是连续的一段字符,而子序列不需要。

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
class Solution {
public:
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
if (A.size() == 0 || B.size() == 0) return 0;
int result = 0;
vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++) {
if (i == 0 || j == 0)
dp[i][j] = (A[i] == B[j] ? 1 : 0);
else {
if (A[i] == B[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = 0;
}
result = max(result, dp[i][j]);
}
}
return result;
}
};

###最长公共子序列问题

Given two strings, find the longest common subsequence (LCS).

引入一个数组$dp$,$dp[i,j]$表示$X[i],Y[j]$的字长公共子序列的长度,那么递推关系如下:

$$
dp[i,j] =
\begin{cases}
0, & \mbox{if } i = 0 \mbox{ or } j = 0 \\
dp[i - 1, j - 1] + 1, & \mbox{if } i,j>0 \mbox{ and } x_i = y_j \\
max(dp[i - 1, j], dp[i, j - 1]) & \mbox{if } i,j>0 \mbox{ and } x_i \neq y_j
\end{cases}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
int longestCommonSubsequence(string A, string B) {
if (A.size() == 0 || B.size() == 0) return 0;
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[A.size()][B.size()];
}
};