动态规划
就是从 s 到 t 的最小步数是多少 （s 到 t 和 t 到 s 是等价的，所以怎么方便怎么来）
之所以是 dp 是因为我们处理好了比如 s 的一个前缀到 t 的一个前缀，那么到了下一个位置的时候，可以从前面的状态转移过来，因为只需要考虑当前的两个元素是否相同
如果相同，那么直接从 dp[i-1][j-1] 转移过来
否则的话，从 dp[i-1][j-1], dp[i][j-1], dp[i-1][j]，分别代表替换（位置i），插入，删除（位置i）
注意因为有空集的情况所以 dp 要开 n+1
但是遍历的时候和字符串的映射要减一
class Solution {
public:int minDistance(string s, string t) {int n = s.size(), m = t.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));iota(dp[0].begin(), dp[0].end(), 0);for (int i = 0; i <= n; i++) {dp[i][0] = i;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1];} else {dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;}}}return dp[n][m];}
};