leetcode72难动态规划

leetcode72难动态规划

题意;经由最小的操作数把串S变为串T：

理论bfs是可行的的。

转化为对其字符串问题，

对于空字符：

s的字符为添加，T的字符为减少

不同则为修改。

用dpij表示最少得分，加一个数组sameij表示ij是否相等。

三种情况：1上面已讲

2.dpi-1j+1 也就是s的第i个字符和空对其，即删除

3.dpij-1+1添加

初值： dp0j=j dpi0=i

注意：每个i正向循环j   dpi-1j-1已经是新值了。

class Solution {public: int minDistance(string word1, string word2) { int m = word1.length(), n=word2.length(); vector > dp(m+1,vector(n+1)); for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0){ dp[i][j]=j; } else if(j==0){ dp[i][j]=i; } else { dp[i][j] = min(dp[i-1][j-1]+((word1[i-1]==word2[j-1])?0:1), min(dp[i][j-1]+1,dp[i-1][j]+1) ); } } } return dp[m][n]; }};

然后减了一维的空间：

class Solution {public: int minDistance(string word1, string word2) { int m = word1.length(), n=word2.length(); vector dp(n+1); for(int i=0;i<=m;i++){ int last; for(int j=0;j<=n;j++){ if(i==0){ dp[j]=j; } else if(j==0){ last=dp[j]; dp[j]=i; } else { int temp = dp[j]; dp[j] = min(last+((word1[i-1]==word2[j-1])?0:1), min(dp[j-1]+1,dp[j]+1) ); last=temp; } } } return dp[n]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。