class Solution {
public:
int minDistance(string word1, string word2) {
int m,n;
m=word1.size();
n=word2.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=0;i<=n;i++){
dp[0][i]=i;
}
for(int i=0;i<=m;i++){
dp[i][0]=i;
}
for(int i=1;i<=m;++i){
for(int j=1;j<=n;j++){
int left=dp[i-1][j]+1;
int right=dp[i][j-1]+1;
int mid=dp[i-1][j-1];
if(word1[i-1]!=word2[j-1])
mid+=1;
dp[i][j]=min(left,min(right,mid));
}
}
return dp[m][n];
}
};
2.最大矩阵
方法一：动态规划
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<vector<int>> left(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == ‘1‘) {
left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == ‘0‘) {
continue;
}
int width = left[i][j];
int area = width;
for (int k = i - 1; k >= 0; k--) {
width = min(width, left[k][j]);
area = max(area, (i - k + 1) * width);
}
ret = max(ret, area);
}
}
return ret;
}
};
