Code & Func

第48天。

今天的题目是Maximum Length of Repeated Subarray:

一道DP的题目，有点像LCS。

我们假定dp[i, j]为以A[i]结尾和以B[j]结尾的最长重合子数组的长度，则：

$$ dp[i, j] = \left{ \begin{aligned} 0 &, & A[i] \neq B[i] \ dp[i-1, j-1] + 1 &, & A[i] = B[i] \end{aligned} \right. $$

然后我们只需要对dp求最大值即可得到最长重复子数组的长度：

1
int findLength(vector<int>& A, vector<int>& B) {
2
    int n = A.size();
3
    if (n == 0) return 0;
4

5
    vector<int> dp(n+1, 0);
6
    int res = 0;
7
    for(int i = 1;i <= n; i++) {
8
        for(int j = n;j >= 1; j--) {
9
            dp[j] = (A[i-1] == B[j-1]) ? (dp[j-1] + 1) : 0;
10
            res = max(dp[j], res);
11
        }
12
    }
13

14
    return res;
15
}

来多一道Edit Distance:

一道hard的题目，一次直接AC了。也是DP的题目，这道题让人觉得麻烦的是，它支持三种操作：

插入
删除
替换

一开始会觉得，插入和删除有点难区分，后来想了想，好像他们的代价是一样的，所以我们可以只用删除，不用插入，所以我们可以来解决这个问题：

dp[i, j]为word1[0..i]和word2[0..j]的编辑距离：

如果word1[i] == word2[j]的话，dp[i,j] = dp[i-1, j-1]，即不需要做任何编辑
如果word1[i] != word2[j]的话，我们可以尝试删除或替换两种操作
- 删除word1[i]
- 删除word2[i]
- 替换word1[i]或word2[i]

则dp[i, j] = min(dp[i-1, j], dp[i, j-1], dp[i-1, j-1])

边界条件就是，当i==0时，dp[i, j] = j,当j==0时，dp[i, j] = i。

所以我们可以写出动规方程：

$$ dp[i, j] = \left{ \begin{aligned} i &, & i = 0 \ j &, & j = 0 \ dp[i-1, j-1] &, & word1[i] = word2[j] \ min(dp[i-1, j], dp[i, j-1], dp[i-1, j-1]) &, & A[i] \neq B[i] \end{aligned} \right. $$

因此，代码如下：

1
int minDistance(string word1, string word2) {
2
    int n1 = word1.size(), n2 = word2.size();
3
    vector<int> dp(n2 + 1);
4
    for(int j = 0;j <= n2; j++) {
5
        dp[j] = j;
6
    }
7
    int prev;
8
    for(int i = 1; i <= n1; i++) {
9
        prev = dp[0];
10
        dp[0] = i;
11
        for(int j = 1;j <= n2; j++) {
12
            swap(dp[j], prev);
13
            if (word1[i-1] != word2[j-1]) {
14
                dp[j] = min(min(dp[j-1], dp[j]), prev) + 1;
15
            }
4 collapsed lines
16
        }
17
    }
18
    return dp[n2];
19
}