[算法笔记]最长递增子序列和编辑距离

最长递增子序列

例如对于

a[] = {2,1,5,3,6,4,8,9,7}
1

其最长递增子序列为{1,3,4,8,9}所以长度（或者说是结果）为5。

---

对于a[0...n-1]，用dp[i]表示a[0...i]中以a[i]结尾的最长递增子序列长度

其状态状态方程：

dp[i]=1						// 0≤i≤n-1
dp[i]=max(dp[i],dp[j]+1])	// 若a[i]>a[j], 0≤i≤n-1, 0≤j≤i-1
// 第二种情况其实就是第i个和之前所有的比一遍，看看
1
2
3

其实就是对于a[i]，跟前面的比，看看能不能组成更长的（a[i]是否大于a[j]），能（大于）就在状态表里拿到原来的数据（dp[j]）并+1（dp[i]=dp[j]+1），不能（小于）就把它这个状态写为1（dp[i]=1）

它也是提前把dp填充一遍，填充为1

/**
 * @param arr int整型一维数组 给定的数组
 * @param arrLen int arr数组长度
 * @return int整型
 */
int LIS(int* arr, int arrLen ) {
    // write code here
    if(arrLen==0)return 0;
    int dp[1001];
    int max = 1;
    for(int i = 0; i < arrLen; ++i){
        dp[i]=1;
        for(int j = 0;j < i;++j){
            if(arr[i]>arr[j]){
                dp[i]=dp[i]>dp[j]+1?dp[i]:dp[j]+1;
            }
        }
        if(max < dp[i])max = dp[i];
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

两重循环，时间复杂度$O(n)$

相关问题：[牛客]BM71 最长上升子序列(一)

---

大佬代码：

int LIS(int* arr, int arrLen ) {
    // write code here
    if(arrLen<=1) return arrLen;
    int list[1000]={0}, end=0;
    list[0]=arr[0];
    for(int i=1; i<arrLen; i++)
    {
        if(arr[i]>list[end])
        {
            list[++end]=arr[i];
        }
        else if(arr[i]<list[end])
        {
            int high=end, low=0, mid;
            while(high>=low)
            {
                mid=low+(high-low)/2;
                if(list[mid]==arr[i]) break;
                else if(list[mid]>arr[i])
                {
                   high=mid-1;
                }
                else
                {
                   low=mid+1;
                }
            }
            if(list[mid]>arr[i]) list[mid]=arr[i];
            else if(list[mid]<arr[i]) list[mid+1]=arr[i];
        }
    }
    return end+1;
}
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

编辑距离

编辑距离问题就是：

设A和B是两个字符串。现在要用最少的字符操作次数，将字符串A转换为字符串B。

其中字符操作共有3种：

1. 插入一个字符
2. 删除一个字符
3. 将一个字符替换另一个字符

例如A="sfdqxbw"，B="gfdgw"，结果为4

---

设计一个动态规划二维数组dp，其中dp[i][j]表示将a[0..i-1](1≤i≤m)与b[0..j-1](1≤j≤n)的最优编辑距离（即a[0..i-1]转换为b[0..j-1]的最少操作次数）

分两种情况：一是B全空，则结果为A.length()（当然，A空也类似），另一种则是两队均非空，此时每个串都取1个字符作为比较串，比较这两串各自最后的字符，依据操作结果，扩大串的规模，进行后续操作

dp[i][j]是a[0...i]和b[0...j]最小编辑距离

由此，增删改的操作对于dp[i][j]的下标变化也是不一样的：

// a[i-1]替换为b[j-1]
dp[i][j]=dp[i-1][j-1]+1
// a[i-1]后面插入b[j-1]
dp[i][j]=dp[i][j-1]+1
// 删除a[i-1]
dp[i][j]=dp[i-1][j]+1
1
2
3
4
5
6

故有状态转移方程：

// 当a[i-1]=b[j-1]
dp[i][j]==dp[i-1][j-1]
// 当a[i-1]≠b[j-1]
dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j-1]+1,dp[i-1][j]+1)
1
2
3
4

一开始思考，这个“后面插入”也不是很直观。然而比如说对于A="sfdqxbw"，B="gfdgw"，那么dp[2][3]就是"sf"和""gfd，这里最优操作是有“后面插入”这一步的。即先“后面插入”d，然后再修改s为g，总共为2。正是因为“后面插入”，才不能保证前面的内容和B中的相同，所以才有dp[i][j]=dp[i][j-1]+1。

所有状态转移方程中，所有的下标减一都是因为原先的位置已经解决了，可以缩小规模。

不严格地说，这个dp数组是有边界条件的，如下：

for(int i = 1; i < a.length(); ++i){
	dp[i][0]=i;
}
for(int j = 1; j < b.length(); ++j){
	dp[0][j]=j;
}
1
2
3
4
5
6

---

相关题目：[牛客]BM75 编辑距离(一)

class Solution {
public:
    int editDistance(string str1, string str2) {
        // write code here
        if(str1.length() == 0){
            return str2.length();
        }
        else if(str2.length() == 0){
            return str1.length();
        }
        int dp[1001][1001];
        for(int i = 1; i <= str1.length(); ++i){
            dp[i][0]=i;
        }
        for(int j = 1; j <= str2.length(); ++j){
            dp[0][j]=j;
        }
        for(int i = 1; i <=str1.length();++i){
            for(int j = 1; j <= str2.length(); ++j){
                if(str1[i-1] == str2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j]=min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
};
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

然后例行仰望大佬代码

class Solution {
public:
    int editDistance(string str1, string str2) {
        int m=str1.size(),n=str2.size();
        vector<vector<int>> dp(2,vector<int>(n+1,0));
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1;i<=m;i++){
            dp[i%2][0]=i;
            for(int j=1;j<=n;j++){
                if(str1[i-1]==str2[j-1])
                    dp[i%2][j]=dp[(i-1)%2][j-1];
                else dp[i%2][j]=min({dp[(i-1)%2][j],dp[i%2][j-1],dp[(i-1)%2][j-1]})+1;
            }
        }
        return dp[m%2][n];
        // write code here
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

没用数组用的vector，节省空间。

然后是这个对2取余的操作。将dp由8*3缩减到了2*4（2行4列），事实上无论输入是什么，dp都是两行n列，n取决于str2长度

还是以题目输入为例："nowcoder"和"new"

// 这是正常解法的dp结果
// printf("%d ",dp[i][j]);
0 1 2 3
1 0 1 2
2 1 1 2
3 2 2 1
4 3 3 2
5 4 4 3
6 5 5 4
7 6 5 5
8 7 6 6
1
2
3
4
5
6
7
8
9
10
11

//printf("%d dp[%d][%d] = %d\n",i,i%2,j,dp[i%2][j]);
1 dp[1][1] = 0
1 dp[1][2] = 1
1 dp[1][3] = 2
// ---人为添加的横线1---
2 dp[0][1] = 1
2 dp[0][2] = 1
2 dp[0][3] = 2
3 dp[1][1] = 2
3 dp[1][2] = 2
3 dp[1][3] = 1
4 dp[0][1] = 3
4 dp[0][2] = 3
4 dp[0][3] = 2
5 dp[1][1] = 4
5 dp[1][2] = 4
5 dp[1][3] = 3
6 dp[0][1] = 5
6 dp[0][2] = 5
6 dp[0][3] = 4
7 dp[1][1] = 6
7 dp[1][2] = 5
7 dp[1][3] = 5
8 dp[0][1] = 7
8 dp[0][2] = 6
8 dp[0][3] = 6
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

截止我“人为添加的横线1”那里，此时两种方法的dp数组内容是一样的，即

0 1 2 3
1 0 1 2
1
2

然后，原先方法本应该写dp[2][j]，并dp[2][j]用到了dp[1][j]的数据。此时还好，但是对于dp[i][j]，会用到dp[i][j]的数据。因为对于dp[i][j]，总是和上方。左方，和左上方三个格子比较，此时涉及两行内容，即第i行和第i-1行。

但是在新方法里面没有，那么多，只有两行，不过不要紧，把i=2行数据写到第0行，此时第一行就是i-1=1行的数据，会被用到。

同理，写入i%2行时，(i-1)%2总是它的上一行。

某种程度上，可以理解为滑动窗口

在代码中的体现就是：

if(str1[i-1]==str2[j-1])
	dp[i%2][j]=dp[(i-1)%2][j-1];
else
	dp[i%2][j]=min({dp[(i-1)%2][j],dp[i%2][j-1],dp[(i-1)%2][j-1]})+1;
1
2
3
4

再回去看两种方法的最后两行，发现内容是一样的（除了两行颠倒了一下），也得到了印证。

不难发现，取余dp的应用条件在于，最后的结果不会出现在dp的任意位置。

在本例中，结果只能是dp的右下角。所以不会再用到前面的信息，可以被覆写掉。

另外还需要注意的是下列代码的位置

dp[i%2][0]=i;
1

因为行是滚动的，所以行首也是再变的，因此在每次i变化时，动态载入的行首（放在for循环内）。