社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
想到动态规划是第一步,其次hhh。
先看官方解释:
dp[i][j]表示str1前i个字符与str2前j个字符匹配所需的最少次数;str1="horse",str2="ros"
当我们知道dp[i][j],dp[i+1][j],dp[i][j+1]后就可以分两种情况来讨论了;
1---当str1[i+1]=str2[j+1]时,就等于给的例子中,匹配hors和ros时;
dp[i+1][j+1]=1+{dp[i][j]-1,dp[i][j+1],dp[i+1][j]};
我们一个一个看;最重要的是前面的1代表的是什么操作;
dp[i][j]表示hor,ro匹配的最少次数,你管我怎么匹配得到的,反正我现在已经得到ro了,那么最后的s就不用特殊处理了;所以-1+1=0;
dp[i][j+1]表示hor,ros匹配的最少次数,我都匹配完了,直接把刚加入的s给删掉不就行了,所以1对应的是删除操作;
dp[i+1][j]表示hors,ro匹配的最少次数,同样的,我在最后再添加一个s不就得了,所以这里1对应的是插入操作;
------------更新
实际上;对于上面这种情况,是不需要取最小值的;
我们比较 dp[i][j]-1(表示hor,ro匹配的最少次数),dp[i][j+1]的大小(表示hor,ros匹配的最少次数);
等价于比较dp[i][j]和dp[i][j+1]+1的大小;dp[i][j+1]+1中的1可以看做hor匹配ro,最后加上一个s;有没有发现是等于dp[i][j]的;但这不一定是最优解
所以dp[i][j+1]+1>=dp[i][j];
同理我们比较dp[i][j]和dp[i-+1][j]+1的大小;我的1可以看做删除hors后面的s,这消耗一个操作,就等价于dp[i][j]了;
所以dp[i+1][j]+1>=dp[i][j];
所以压根不需要比较,此时可以直接得出dp[i+1][j+1]==dp[i][j];
-------------
2---当str1[i+1]=str2[j+1]时,就等于给的例子中,匹配horse和ros时;
dp[i+1][j+1]=1+{dp[i][j],dp[i][j+1],dp[i+1][j]};
同样的----
dp[i][j]表示hors,ro匹配的最少次数,你管我怎么匹配得到的,反正我现在已经得到ro了,那么最后的e直接替换成s不就得了;
所以这里的1代表的是替换操作;
dp[i][j+1]表示hors,ros匹配的最少次数,我都匹配完了,直接把刚加入的e给删掉不就行了,所以1对应的是删除操作;
dp[i+1][j]表示horse,ro匹配的最少次数,同样的,我在最后再添加一个s不就得了,所以这里1对应的是插入操作;
后两种情况其实和上面第一种情况分析一样,唯一不同的是对dp[i][j]的分析;
dp[0][0]=0;
dp[0][i]=i;//表示i个插入操作
dp[i][0]=i;//表示i个删除操作
修改后(我还是很无语,好像同一个答案每次提交结果不是一样的,相差几ms,但这却足以让单题排名差距很大hhh)
----------------------------------------------------------------------------------------------------------------------------------------------
内存消耗这块我用两个等长数组代替了二维数组hhh,很多题目都可以这样做。。。
class Solution {
public:
int minDistance(string word1, string word2) {
int N = word1.length();
int M = word2.length();
if (M == 0)
return N;
//vector<vector<int>>v(N+1, vector<int>(M+1, 0));
vector<int>v(1+N, 0);
vector<int>v2(N+1, 0);
//边界初始化
for (int i = 0; i <= N; i++) {
v[i] = i;
}
for (int i = 1; i <= M; i++) {
v2[0] = i;
for (int j = 1; j <= N; j++) {
int tem = (word2[i-1] == word1[j-1]) ? 1 : 0;
v2[j] = 1 + min(min(v[j - 1] - tem, v[j]), v2[j-1]);
//cout << word1.substr(0, i) << " " << word2.substr(0, j) << " " << v2[j] << endl;
}
v = v2;
}
return v2[N];
}
};
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!