开个坑。感觉算法题还是要经常练保持手感，前段时间蓝桥杯，感觉大一时洛谷那么多题白刷了，那么多算法模板白总结了，都忘完了。做算法题还是要尽量自己多想，不思考看题解忘得太快。虽然最近比较忙，但每两天做一点应该还是可以的（吧）。希望不咕。

一维

T198. House Robber

假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果 你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。

输入是一个一维数组，表示每个房子的钱财数量；输出是劫匪可以最多抢劫的钱财数量。

思路

很基础的dp，dp[i]表示前i个房子劫匪最多抢劫的数量，那么它有两种情况组成：一种是我们选择不抢劫这个房子，此时累计的金额即为 dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2]。因此本题的状态转移方程为 dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])。

1
2
3
4
5
6
7
8
9
int rob(vector<int>& nums) {
	int n = nums.size(); 
	vector<int> dp(n+1, 0);
	dp[1] = nums[0];
	for(int i = 2; i <= n; i++) {
		dp[i] = max(dp[i-2]+nums[i-1], dp[i-1]);
	}
	return dp[n];
}

当然由于递推到dp[i]时，本数组此前有用的值只有dp[i-1]与dp[i-2]，所以可以简单状态压缩：用三个变量来代替这三个数，节省空间。

1
2
3
4
5
6
7
8
9
10
int rob(vector<int>& nums) { 
    if (nums.empty()) return 0; 
    int n = nums.size(); 
    if (n == 1) return nums[0]; 
    int pre2 = 0, pre1 = 0, cur; 
    for (int i = 0; i < n; ++i) { 
        cur = max(pre2 + nums[i], pre1); pre2 = pre1; pre1 = cur;
    } 
    return cur; 
}

T413. Arithmetic Slices

给定一个数组，求这个数组中连续且等差的子数组一共有多少个。

输入是一个一维数组，输出是满足等差条件的连续字数组个数。

1
2
Input: nums = [1,2,3,4] 
Output: 3  // 等差数列有 [1,2,3]、[2,3,4] 和 [1,2,3,4]

思路

对于[1,2,3,4]，在尾部加一个5，那么原来以4结尾的等差数列，增加了一个元素，它们的数量不变。但同时会形成一个新的数列[3,4,5]。因此设dp[i]表示以nums[i]结尾的等差数列的个数。

递推关系：如果A[i]-A[i-1] = A[i-1]-A[i-2]，则dp[i]=1+dp[i-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
int numberOfArithmeticSlices(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;
    if (n < 3) return 0;
    vector<int> dp(n, 0);
    for(int i = 2; i < n; i++) {
        if (nums[i]-nums[i-1] == nums[i-1]-nums[i-2]) {
            dp[i] = dp[i-1] + 1;
        } 
        ans += dp[i];
    } 
    return ans;
}

二维

T64. Minimum Path Sum

给定一个m × n 大小的非负整数矩阵，求从左上角开始到右下角结束的、经过的数字的和最小的路径。每次只能向右或者向下移动。

1
2
Input: [[1,3,1], [1,5,1], [4,2,1]] 
Output: 7

思路：

很基础的二维dp，思路很好想：dp[i][j]表示左上角开始到(i,j)处最小路径的数字和。那么状态转移方程为：

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。当然边界要特判一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int minPathSum(vector<vector<int> > &grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int> > dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0)
                dp[i][j] = grid[i][j];
            else if (i == 0)
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            else if (j == 0)
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            else
                dp[i][j] = min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
        }
    }
    return dp[m - 1][n - 1];
}

空间压缩：因为 dp 数组的值由左边和上边转移而来，对于第 i 行，在遍历到第 j 列的时候，因为第j-1列已经更新过了，所以dp[j-1]代表dp[i][j-1] 的值；而 dp[j] 还未更新，此时的值是在第 i-1 行的时候计算的，因此可以代表 dp[i-1][j] 的值。这样就把dp数组压成一维的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int minPathSum(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, 0);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == 0 && j == 0) {
                dp[j] = grid[i][j];
            } else if (i == 0) {
                dp[j] = dp[j - 1] + grid[i][j];
            } else if (j == 0) {
                dp[j] = dp[j] + grid[i][j];
            } else {
                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
    }
    return dp[n - 1];
}

T542. 01 Matrix

给定一个由 0 和 1 组成的二维矩阵，求每个位置到最近的 0 的距离

和上一题主要的区别在于本次矩阵需要四个方向的搜索，我们就不能简单由上方和左方矩阵转移而来。我们可以从左上到右下进行一次 dp ，再从右下到左上进行一次 dp 。

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
#define INF 0x3fffffff
vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0) {
                dp[i][j] = 0;
            } else {
                if (i == 0 && j == 0) {
                    dp[i][j] = INF;	// 注意 inf 的设置
                } else if (i == 0) {
                    dp[i][j] = dp[i][j - 1] + 1;
                } else if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + 1;
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
    }
    // 这里开始不一样，需要和之前dp所得的成果相比，取最小
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (matrix[i][j] != 0) {
                if (i == n - 1 && j == m - 1) {
                    dp[i][j] = min(INF, dp[i][j]);
                } else if (i == n - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
                } else if (j == m - 1) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
                } else {
                    dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j + 1]) + 1);
                }
            }
        }
    }
    return dp;
}

T221. Maximal Square

给定一个二维的 0-1 矩阵，求全由 1 构成的最大正方形面积。

悬线法

悬线法常用来求解这种给定矩阵中满足条件的最大子矩阵。

首先我们用left[i][j]表示从(i,j)能到达的最左位置，用right[i][j]表示从(i,j)能到达的最右位置，用up[i][j]表示从(i,j)向上扩展的最长长度。

那么这道题：

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
43
44
45
46
int maximalSquare(vector <vector<char>> &matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> left(n, vector<int>(m, 0));
    vector<vector<int>> right(n, vector<int>(m, 0));
    vector<vector<int>> up(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 能到达的最右和最左都初始化为自己开始的横坐标
            left[i][j] = j;
            right[i][j] = j;
            up[i][j] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < m; j++) {	// 注意 j 是最作坊元素的右边元素位置，因为要递推
            if ((matrix[i][j] == '1') && (matrix[i][j - 1] == '1')) {
                left[i][j] = left[i][j - 1];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = m - 2; j >= 0; j--) {	// 这里 j 类似
            if ((matrix[i][j] == '1') && (matrix[i][j + 1] == '1')) {
                right[i][j] = right[i][j + 1];
            }
        }
    }
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0 && (matrix[i][j] == '1') && (matrix[i - 1][j] == '1')) { // i类似
                left[i][j] = max(left[i][j], left[i - 1][j]); 
                // 上下的left取最靠右的，确保满足
                right[i][j] = min(right[i][j], right[i - 1][j]);
                up[i][j] = up[i - 1][j] + 1;
            }
            if (matrix[i][j] == '1') {
                int len = right[i][j] - left[i][j] + 1;
                int height = min(len, up[i][j]);
                area = max(area, height * height);
            }
        }
    }
    return area;
}

常规的 dp 转移

dp[i][j] 表示满足题目条件的、以 (i, j) 为右下角的正方形或者长方形的属性。对于本题，则表示以 (i, j) 为右下角的全由 1 构成的最大正方形边长。如果当前位置是 0，那么 dp[i][j] 即为 0；如果当前位置是 1，我们假设 $dp[i][j]=k$，其充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须 都不小于$(k-1)$，否则 (i, j) 位置不可以构成一个边长为 k 的正方形。同理，如果这三个值中的 的最小值为 k − 1，则 (i, j) 位置一定且最大可以构成一个边长为 k 的正方形。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) { 
        return 0;
    }
    int m = matrix.size(), n = matrix[0].size(), max_side = 0; 
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); 
    for (int i = 1; i <= m; ++i) { 
        for (int j = 1; j <= n; ++j) { 
            if (matrix[i-1][j-1] == '1') { 
                dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
            } 
            max_side = max(max_side, dp[i][j]); 
        } 
    } 
    return max_side * max_side;
}

分割

T279. Perfect Squares

给定一个正整数，求其最少可以由几个完全平方数相加构成。

dp[i] 表示数字 i 最少可以由几个完全平方数相加构成。那么它可以由 $i-k^2$的数加$k^2$得到，组成数+1。遍历一下可能的 k 即可。

1
2
3
4
5
6
7
8
9
10
int numSquares(int n) {
    vector<int> dp(n + 1, INT32_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

T91. Decode Ways

已知字母A-Z可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个 数字串。

eg：

1
2
Input: "226" 
Output: 3	// BZ(2 26)、VF(22 6) BBF(2 2 6)

用dp[i]表示前 i 个数字可以等价于多少字符串。那么s[0:i]可以由s[0:i-1]加一个1~9的数字组成，也可以由s[0:i-2]加一个10~26的数字组成，注意 01 并不代表一个字符。

注意多考虑一些特殊情况就好

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
int numDecodings(string s) {
    int len = s.size();
    vector<int> dp(len + 1, 0);
    if (s[0] == '0') { return 0; }
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= len; i++) {
        int num1 = s[i - 1] - '0';
        int num2 = 10 * (s[i - 2] - '0') + num1;
        if (num1 > 0) {
            dp[i] = dp[i - 1];
        } else {
            if (0 < num2 && num2 <= 26) {
                dp[i] = dp[i - 2];
                continue;
            } else {
                return 0;
            }
        }
        if (0 < num2 && num2 <= 26 && s[i - 2] != '0') {
            dp[i] += dp[i - 2];
        }
    }
    return dp[len];
}

T139. Word Break

给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字符串都可以在集合内找到。

eg:

1
2
Input: s = "applepenapple", wordDict = ["apple", "pen"] 
Output: true

在考虑每个分割位置时，遍历一下字符串集合，以确定当前位置是否可以成功分割。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool wordBreak(string s, vector<string> &wordDict) {
    int len = s.size();
    vector<bool> dp(len + 1, false);
    dp[0] = true;
    for (int i = 1; i <= len; i++) {
        for (const string &word: wordDict) {
            int wordLen = word.size();
            if (i - wordLen >= 0 
                && (s.substr(0, i - wordLen) + word == s.substr(0, i))) {
                dp[i] = dp[i] || dp[i - wordLen];
            }
        }
        cout << dp[i] << endl;
    }
    return dp[len];
}

子序列

T300. Longest Increasing Subsequence

给定一个未排序的整数数组，求最长的递增子序列。

dp[i]表示以index为i处数字结尾的最长子序列长度。

$O(n^2)$解法很好想：遍历i之前所有加上i处的数还是递增的序列，找到长度最大的一个就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int> &nums) {
    int len = nums.size();
    vector<int> dp(len + 1, 1);
    int ans = 0;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}

可以使用二分查找将时间复杂度降低为$O(n log n)$。我们定义一个dp数组，其中 dp[k]
存储长度为 k+1 的最长递增子序列的最后一个数字。我们遍历每一个位置 i，如果其对应的数字 大于 dp 数组中所有数字的值，那么我们把它放在 dp 数组尾部，表示最长递增子序列长度加 1； 如果我们发现这个数字在 dp 数组中比数字 a 大、比数字 b 小，则我们将 b 更新为此数字，使得之后构成递增序列的可能性增大（贪心的思想）。以这种方式维护的 dp 数组永远是递增的，因此可以用二分查找加速搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLIS(vector<int> &nums) {
    int n = nums.size();
    if (n <= 1) return n;
    vector<int> dp;
    dp.push_back(nums[0]);
    for (int i = 1; i < n; ++i) {
        if (dp.back() < nums[i]) {
            dp.push_back(nums[i]);
        } else {
            // lower_bound 返回一个指针，想获得数组下标要 -dp
            auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);
            *itr = nums[i];
        }
    }
    return dp.size();
}

T1143. Longest Commom Subsequence

给定两个字符串，求它们最长的公共子序列长度

dp[i][j]表示到第一个字符串位置 i 为止、到第二个字符串位置 j 为止、最长的公共子序列长度。让 i 和 j 从 1 开始能避免繁琐的临界判断。

状态转移方程，画个图看看规律就懂了。由于没重复扫描，也不用和自身比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.size();
    int len2 = text2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[len1][len2];
}

时间复杂度 && 空间复杂度：$O(MN)$

背包问题

有 N 个物品和容量为W 的背包，每个物品都有自己的体积w和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

0-1背包

dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。在我们遍历到第 i 件物品时，在当前背包总容量为 j 的情况下，如果我们不将物品 i 放入背包，那么 dp[i][j] = dp[i-1][j]，即前 i 个物品的最大价值等于只取前 i-1 个物品时的最大价值；如果我们将物品 i 放 入背包，假设第 i 件物品体积为w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v。我们只需 在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为O(NW)。

1
2
3
4
5
6
7
8
9
10
11
12
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 0; j <= W; ++j) {
            if (j >= w) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v);
            } else { dp[i][j] = dp[i - 1][j]; }
        }
    }
    return dp[N][W];
}

空间压缩：$O(W)$

遍历weight的时候必须逆向遍历，若按照从左往右的顺序进行正向遍历，则 dp[j-w] 的值在遍历到 j 之前就已经被更新成物品 i 的值了

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = W; j >= w; --j) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    return dp[W];
}

完全背包

在完全背包问题中，一个物品可以拿多次。假设我们遍历到物品 i = 2，且其体积为w = 2，价值为 v = 3；对于背包容量 j = 5，最多只能装下 2 个该物品。那么我们的状 态转移方程就变成了 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW) 的 时间复杂度。 怎么解决这个问题呢？我们发现在 dp[2][3] 的时候我们其实已经考虑了 dp[1][3] 和 dp[2][1]的情况，而在时 dp[2][1] 也已经考虑了 dp[1][1] 的情况。因此，如图下半部分所示，对于拿多个 物品的情况，我们只需考虑 dp[2][3] 即可，即 dp[2][5] = max(dp[1][5], dp[2][3] + 3)。这样，我们就得到了完全背包问题的状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)，其与 0-1 背包问 题的差别仅仅是把状态转移方程中的第二个 i-1 变成了 i

1
2
3
4
5
6
7
8
9
10
11
12
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; ++i) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = 0; j <= W; ++j) {
            if (j >= w) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w] + v);
            } else { dp[i][j] = dp[i - 1][j]; }
        }
    }
    return dp[N][W];
}

空间压缩：$O(W)$

遍历weight的时候必须正向遍历，因为我们需要利用当前物品在第 j-w 列的信息

1
2
3
4
5
6
7
8
9
10
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; ++i) {
        int w = weights[i - 1], v = values[i - 1];
        for (int j = w; j <= W; ++j) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    return dp[W];
}

T474. Ones and Zeroes

给定m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。

1
2
3
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 
Output: 4
在这个样例中，我们可以用 5 个 0 和 3 个 1 构成 [“10”, “0001”, “1”, “0”]。

我们这么想，所有的字符串可以看作物品，现在要往背包里面装，背包体积限制为（5，3），每成功装进背包一个字符串，背包总价值就+1。现在求的就是背包的最大总价值。因此这实际上是一个和0-1背包，只不过物品扩展到了两维度。

dp[i][j][k] 表示前 i 件物品 0 的数量不超过 j ，1的数量不超过 k 的情况下能达到的最大价值。

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
int findMaxForm(vector<string> &strs, int m, int n) {
    int N = strs.size();
    int dp[N + 1][m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    int count_zero[N];
    for (int i = 0; i < N; i++) {
        int count = 0;
        for (int j = 0; j < strs[i].size(); j++) {
            if (strs[i][j] == '0') count++;
        }
        count_zero[i] = count;
    }
    for (int i = 1; i <= N; i++) {
        int wei_zero = count_zero[i - 1], wei_one = strs[i - 1].size() - count_zero[i - 1];
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j >= wei_zero && k >= wei_one) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - wei_zero][k - wei_one] + 1);
                } else {
                    dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
    }
    return dp[N][m][n];
}

T322. Coin Change

给定一些硬币的面额，求最少可以用多少颗硬币组成给定的金额。若不存在解，则返回-1

1
2
3
Input: coins = [1, 2, 5], amount = 11 
Output: 3
最少的组合方法是 11 = 5 + 5 + 1。

完全背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
int coinChange(vector<int> &coins, int amount) {
    int N = coins.size();
    int MAX = amount + 2;
    vector<int> dp(amount + 1, MAX);
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        int wei = coins[i - 1];
        for (int j = wei; j <= amount; j++) {
            dp[j] = min(dp[j], dp[j - wei] + 1);
        }
    }
    return dp[amount] == MAX ? -1 : dp[amount];
}

字符串编辑

给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可 以将两个字符串变成相同。

1
2
3
4
5
输入：word1 = "horse", word2 = "ros"
输出：3
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
  • Q：如果 word1[0:i-1] 到 word2[0:j-1] 的变换需要消耗 k 步，那word1[0:i]到 word2[0:j] 的变换需要几步呢？

A：先使用 k 步，把 word1[0..i-1] 变换到 word2[0..j-1]，消耗 k 步。再把 word1[i] 改成 word2[j]，就行了。如果 word1[i] == word2[j]，什么也不用做，一共消耗 k 步，否则需要修改，一共消耗 k + 1 步。

  • Q：如果 word1[0..i-1] 到 word2[0..j] 的变换需要消耗 k 步，那 word1[0..i] 到 word2[0..j] 的变换需要消耗几步呢？

A：先经过 k 步，把 word1[0..i-1] 变换到 word2[0..j]，消耗掉 k 步，再把 word1[i] 删除，这样，word1[0..i] 就完全变成了 word2[0..j] 了。一共 k + 1 步。

  • Q：如果 word1[0..i] 到 word2[0..j-1] 的变换需要消耗 k 步，那 word1[0..i] 到 word2[0..j] 的变换需要消耗几步呢？

A：先经过 k 步，把 word1[0..i] 变换成 word2[0..j-1]，消耗掉 k 步，接下来，再插入一个字符 word2[j], word1[0..i] 就完全变成了 word2[0..j] 了。

综上，word1[0..i] 变换成 word2[0..j] 主要有三种手段，用哪个消耗少，就用哪个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int minDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();

    vector<vector<int>> cost(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; ++i) {
        cost[i][0] = i;
    }
    for (int j = 0; j <= n; ++j) {
        cost[0][j] = j;
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                cost[i][j] = cost[i - 1][j - 1];
            } else {
                cost[i][j] = 1 + min(cost[i - 1][j - 1], min(cost[i][j - 1], cost[i - 1][j]));
            }
        }
    }
    return cost[m][n];
}